star-normal-form.hh

Go to the documentation of this file.

#pragma once

#include <vcsn/algos/constant-term.hh>
#include <vcsn/core/rat/visitor.hh>
#include <vcsn/ctx/fwd.hh>
#include <vcsn/dyn/expression.hh>
#include <vcsn/misc/algorithm.hh> // any_of
#include <vcsn/misc/raise.hh>
#include <vcsn/weightset/b.hh>

namespace vcsn
{

  namespace rat
  {

    /*--------------------------------.
    | star_normal_form(expression).   |
    `--------------------------------*/

    template <typename ExpSet>
    class star_normal_form_visitor
      : public ExpSet::const_visitor
    {
    public:
      using expressionset_t = ExpSet;
      using expression_t = typename expressionset_t::value_t;
      using context_t = context_t_of<expressionset_t>;
      using weightset_t = weightset_t_of<context_t>;
      static_assert(std::is_same<weightset_t, b>::value,
                    "star_normal_form: requires Boolean weights");

      using weight_t = typename weightset_t::value_t;

      using super_t = typename ExpSet::const_visitor;

      constexpr static const char* me() { return "star_normal_form"; }

      enum operation_t { dot, box };

      star_normal_form_visitor(const expressionset_t& rs)
        : rs_(rs)
      {}

      expression_t
      operator()(const expression_t& v)
      {
        operation_ = dot;
        v->accept(*this);
        return std::move(res_);
      }

      VCSN_RAT_VISIT(zero,)
      {
        res_ = rs_.zero();
      }

      VCSN_RAT_VISIT(one,)
      {
        res_ = operation_ == box ? rs_.zero() : rs_.one();
      }

      VCSN_RAT_VISIT(atom, v)
      {
        res_ = rs_.atom(v.value());
      }

      // Plain traversal for sums.
      VCSN_RAT_VISIT(sum, v)
      {
        v.head()->accept(*this);
        expression_t res = res_;
        for (auto c: v.tail())
          {
            c->accept(*this);
            res = rs_.add(res, res_);
          }
        res_ = std::move(res);
      }

      VCSN_RAT_UNSUPPORTED(complement)
      VCSN_RAT_UNSUPPORTED(conjunction)
      VCSN_RAT_UNSUPPORTED(infiltration)
      VCSN_RAT_UNSUPPORTED(ldiv)
      VCSN_RAT_UNSUPPORTED(shuffle)
      VCSN_RAT_UNSUPPORTED(transposition)
      VCSN_RAT_UNSUPPORTED(lweight)
      VCSN_RAT_UNSUPPORTED(rweight)
      using tuple_t = typename super_t::tuple_t;
      virtual void visit(const tuple_t&, std::true_type) override
      {
        raise(me(), ": tuple is not supported");
      }

      VCSN_RAT_VISIT(prod, v)
      {
        if (operation_ == box)
          box_of(v);
        else
          dot_of(v);
      }

      void box_of(const prod_t& v)
      {
        using detail::any_of;
        if (any_of(v,
                   [this](const expression_t& n)
                   {
                     return ws_.is_zero(constant_term(rs_, n));
                   }))
          {
            // Some factor has a null constant-term.
            operation_ = dot;
            dot_of(v);
            operation_ = box;
          }
        else
          {
            // All the factors have a non null constant-term.
            v.head()->accept(*this);
            expression_t res = res_;
            for (auto c: v.tail())
              {
                c->accept(*this);
                res = rs_.add(res, res_);
              }
            res_ = std::move(res);
          }
      }

      void dot_of(const prod_t& v)
      {
        v.head()->accept(*this);
        expression_t res = res_;
        for (auto c: v.tail())
          {
            c->accept(*this);
            res = rs_.mul(res, res_);
          }
        res_ = std::move(res);
      }

      VCSN_RAT_VISIT(star, v)
      {
        if (operation_ == dot)
          {
            operation_ = box;
            v.sub()->accept(*this);
            res_ = rs_.star(res_);
            res_ = rs_.lmul(ws_.star(constant_term(rs_, v.sub())), res_);
            operation_ = dot;
          }
        else
          {
            v.sub()->accept(*this);
          }
      }

    private:
      expressionset_t rs_;
      weightset_t ws_ = *rs_.weightset();
      expression_t res_;
      operation_t operation_ = dot;
    };

  } // rat::

  template <typename ExpSet>
  inline
  typename ExpSet::value_t
  star_normal_form(const ExpSet& rs, const typename ExpSet::value_t& e)
  {
    rat::star_normal_form_visitor<ExpSet> star_normal_form{rs};
    return star_normal_form(e);
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename ExpSet>
      inline
      expression
      star_normal_form(const expression& exp)
      {
        const auto& e = exp->as<ExpSet>();
        return make_expression(e.expressionset(),
                               ::vcsn::star_normal_form(e.expressionset(),
                                                        e.expression()));
      }
    }
  }

} // vcsn::