ratexpset.hh

Go to the documentation of this file.

#ifndef VCSN_CORE_RAT_RATEXPSET_HH
# define VCSN_CORE_RAT_RATEXPSET_HH

# include <set>
# include <string>

# include <vcsn/core/rat/identities.hh>
# include <vcsn/core/rat/printer.hh>
# include <vcsn/core/rat/ratexp.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/weightset/b.hh>
# include <vcsn/weightset/q.hh>
# include <vcsn/weightset/r.hh>
# include <vcsn/weightset/z.hh>
# include <vcsn/weightset/zmin.hh>

namespace vcsn
{
  namespace rat
  {
  template <typename Context>
  class ratexpset_impl
  {
  public:
    using self_type = ratexpset<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_ratexps;
    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>;
    //
    // 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(atom);
    DEFINE(complement);
    DEFINE(inner);
    DEFINE(conjunction);
    DEFINE(leaf);
    DEFINE(ldiv);
    DEFINE(lweight);
    DEFINE(node);
    DEFINE(one);
    DEFINE(prod);
    DEFINE(rweight);
    DEFINE(shuffle);
    DEFINE(star);
    DEFINE(sum);
    DEFINE(transposition);
    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 = self_type;
    using letter_t = self_type;

  public:
    static std::string sname();
    std::string vname(bool full = true) const;
    static self_type make(std::istream& is);

    ratexpset_impl(const context_t& ctx,
                   identities_t identities); // FIXME: make this optional again?

    bool open(bool o) const;

    const context_t& context() const;

    identities_t identities() const;
    bool is_series() const;

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

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

    static bool is_special(value_t v)
    {
      return equals(special(), v);
    }

    bool is_letter(value_t) const
    {
      return false;
    }

    bool is_zero(value_t v) const ATTRIBUTE_PURE;

    static bool is_one(value_t v) ATTRIBUTE_PURE;

    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_one()
    {
      return true;
    }

    static constexpr bool is_ratexpset()
    {
      return true;
    }

    static constexpr bool is_free()
    {
      return false;
    }

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

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

    static bool less_than(value_t l, value_t r);

    static bool equals(value_t l, value_t r);

    static size_t hash(const value_t& l);

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

    // Concrete type implementation.
    value_t zero() const;
    static value_t one();
    value_t add(value_t l, value_t r) const;
    value_t mul(value_t l, value_t r) const;
    value_t concat(value_t l, value_t r) const;
    value_t conjunction(value_t l, value_t r) const;
    value_t shuffle(value_t l, value_t r) const;
    value_t ldiv(value_t l, value_t r) const;
    value_t rdiv(value_t l, value_t r) const;
    value_t star(value_t e) const;
    value_t complement(value_t e) const;
    value_t transposition(value_t e) const;
    value_t rmul(value_t e, const weight_t& w) const;
    value_t lmul(const weight_t& w, value_t e) const;
    value_t transpose(value_t e) const;

    word_t word(label_t l) const
    {
      return l;
    }

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

    value_t conv(std::istream& is) const;

    value_t conv(self_type, value_t v) const;

    std::set<value_t> convs(std::istream&) const
    {
      raise(vname(), ": ranges not implemented");
    }

    std::ostream& print(const value_t v, std::ostream& o,
                        symbol format = symbol{"text"}) const;

    std::ostream&
    print_set(std::ostream& o, symbol format = symbol{"text"}) const
    {
      if (format == "latex")
        {
          o << "\\mathsf{";
          switch (identities())
            {
            case identities_t::trivial:
              o << "RatE";
              break;
            case identities_t::series:
              o << "Series";
              break;
            default:
              assert(false);
            };
          o << "}[";
          context().print_set(o, format);
          o << ']';
        }
      else if (format == "text")
        o << vname();
      else
        raise("invalid format: ", format);
      return o;
    }

  private:
    void require_weightset_commutativity() const;
    bool less_than_ignoring_weight_(value_t l, value_t r) const;
    value_t remove_from_sum_series_(values_t addends,
                                    typename values_t::iterator i) const;
    value_t insert_in_sum_series_(const sum_t& addends, value_t r) const;
    value_t merge_sum_series_(const sum_t& addends1, value_t aa2) const;
    value_t add_nonzero_series_(value_t l, value_t r) const;
    type_t type_ignoring_lweight_(value_t e) const;
    weight_t possibly_implicit_lweight_(value_t e) const;
    value_t unwrap_possible_lweight_(value_t e) const;
    value_t mul_expressions_(value_t l, value_t r) const;
    value_t mul_series_(value_t l, value_t r) const;
    value_t mul_(value_t l, value_t r, bool series) const;
    bool is_unweighted_nonsum_(value_t v) const;
    bool is_nonsum_(value_t v) const;
    value_t mul_atoms_(const label_t& l, const label_t& r) const;
    value_t mul_atoms_(const label_t& l, const label_t& r,
                       std::true_type) const;
    value_t mul_atoms_(const label_t& l, const label_t& r,
                       std::false_type) const;
    value_t mul_unweighted_nontrivial_products_(value_t a, value_t b) const;
    value_t mul_products_(value_t a, value_t b) const;
    value_t nontrivial_mul_expressions_(value_t l, value_t r) const;
    value_t nontrivial_mul_series_(value_t l, value_t r) const;

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

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

    value_t concat_(value_t l, value_t r, std::true_type) const;
    value_t concat_(value_t l, value_t r, std::false_type) const;

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

    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;

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

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

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

    template <typename Ctx1, typename Ctx2>
    struct join_impl<ratexpset<Ctx1>, ratexpset<Ctx2>>
    {
      using type = ratexpset<join_t<Ctx1, Ctx2>>;

      static type join(const ratexpset<Ctx1>& lhs, const ratexpset<Ctx2>& rhs)
      {
        return {vcsn::join(lhs.context(), rhs.context()),
                vcsn::join(lhs.identities(), rhs.identities())};
      }
    };

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

      static type join(const letterset<GenSet1>& a, const ratexpset<Ctx2>& 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, ratexpset<Context>>
    {
      using type = ratexpset<Context>;
      static type join(const b&, const ratexpset<Context>& rhs)
      {
        return rhs;
      }
    };

    // Z.
    template <typename Context>
    struct join_impl<z, ratexpset<Context>>
    {
      using context_t = context<labelset_t_of<Context>,
                                join_t<z, weightset_t_of<Context>>>;
      using type = ratexpset<context_t>;
      static type join(const z& ws, const ratexpset<Context>& rs)
      {
        return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
                rs.identities()};
      }
    };

    // Q.
    template <typename Context>
    struct join_impl<q, ratexpset<Context>>
    {
      using context_t = context<labelset_t_of<Context>,
                                join_t<q, weightset_t_of<Context>>>;
      using type = ratexpset<context_t>;
      static type join(const q& ws, const ratexpset<Context>& rs)
      {
        return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
                rs.identities()};
      }
    };

    // R.
    template <typename Context>
    struct join_impl<r, ratexpset<Context>>
    {
      using context_t = context<labelset_t_of<Context>,
                                join_t<r, weightset_t_of<Context>>>;
      using type = ratexpset<context_t>;
      static type join(const r& ws, const ratexpset<Context>& rs)
      {
        return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
                rs.identities()};
      }
    };

    // Zmin.
    template <typename Context>
    struct join_impl<zmin, ratexpset<Context>>
    {
      using context_t = context<labelset_t_of<Context>,
                                join_t<zmin, weightset_t_of<Context>>>;
      using type = ratexpset<context_t>;
      static type join(const zmin& ws, const ratexpset<Context>& rs)
      {
        return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
                rs.identities()};
      }
    };

  }

  template <typename Context>
  ratexpset<Context>
  make_ratexpset(const Context& ctx, rat::identities identities)
  {
    return {ctx, identities};
  }

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

} // namespace vcsn

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

#endif // !VCSN_CORE_RAT_RATEXPSET_HH

// This is ugly, yet I don't know how to address this circular
// dependency another way: ratexpset.hxx uses is-valid-ratexp.hh,
// which, of course, also uses ratexpset.hh.
//
// So let's have ratexpset.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-ratexp.hh>