to-automaton.hh

Go to the documentation of this file.

#pragma once

namespace vcsn
{
  template <Automaton Aut>
  Aut&
  to_automaton(const LabelSet& ls, const typename LabelSet::word_t& w)
    -> mutable_automaton<>
  {

  }

  template <Automaton Aut>
  auto
  eliminate_state(const Aut& aut,
                  state_t_of<Aut> s = Aut::element_type::null_state())
    -> fresh_automaton_t_of<Aut>
  {
    // Get a copy, but be sure to keep the correspondance bw original
    // state numbers and the new ones.
    auto res = make_fresh_automaton<Aut>(aut);
    auto copy = make_copier(aut, res);
    copy();
    if (s != aut->null_state())
      {
        require(aut->has_state(s), "not a valid state: ", s);
        s = copy.state_map().at(s);
      }
    return eliminate_state_here(res, s);
  }


  /*-----------------------.
  | dyn::eliminate_state.  |
  `-----------------------*/

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut, typename Int>
      automaton
      eliminate_state(const automaton& aut, int state)
      {
        const auto& a = aut->as<Aut>();
        using state_t = state_t_of<Aut>;
        auto s = 0 <= state ? state_t(state + 2) : a->null_state();
        return vcsn::eliminate_state(a, s);
      }
    }
  }


  /*----------------------------.
  | to_expression(automaton).   |
  `----------------------------*/

  template <Automaton Aut,
            typename Profiler,
            typename ExpSet = expressionset<context_t_of<Aut>>>
  typename ExpSet::value_t
  to_expression(Aut& a, Profiler& profiler)
  {
    try
      {
        auto eliminate_states = detail::make_state_eliminator(a, profiler);
        eliminate_states();
        return a->get_initial_weight(a->post());
      }
    catch (const std::runtime_error& e)
      {
        raise(e, "  while making expression");
      }
  }

  enum class to_expression_heuristic_t
    {
      best,
      delgado,
      delgado_label,
      naive,
    };

  template <Automaton Aut,
            typename ExpSet = expressionset<context_t_of<Aut>>>
  typename ExpSet::value_t
  to_expression_heuristic(const Aut& aut, vcsn::rat::identities ids,
                          to_expression_heuristic_t algo)
  {
    // State elimination is performed on the lifted automaton.
    auto a = lift(aut, ids);
    using delgado_t = detail::delgado_profiler<decltype(a)>;
    using naive_t = detail::naive_profiler<decltype(a)>;
    switch (algo)
    {
    case to_expression_heuristic_t::best:
      raise("next_state: invalid algorithm: best");

    case to_expression_heuristic_t::delgado:
      {
        auto profiler = delgado_t(a);
        return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
      }

    case to_expression_heuristic_t::delgado_label:
      {
        auto profiler = delgado_t(a, true);
        return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
      }

    case to_expression_heuristic_t::naive:
      {
        auto profiler = naive_t(a);
        return to_expression<decltype(a), naive_t, ExpSet>(a, profiler);
      }
    }
    BUILTIN_UNREACHABLE();
  }

  template <Automaton Aut,
            typename ExpSet = expressionset<context_t_of<Aut>>>
  typename ExpSet::value_t
  to_expression(const Aut& aut, vcsn::rat::identities ids,
                to_expression_heuristic_t algo)
  {
    if (algo == to_expression_heuristic_t::best)
      {
        typename ExpSet::value_t best;
        auto best_size = std::numeric_limits<size_t>::max();
        for (auto a: {to_expression_heuristic_t::delgado,
                      to_expression_heuristic_t::delgado_label,
                      to_expression_heuristic_t::naive})
          {
            auto r = to_expression_heuristic<Aut, ExpSet>(aut, ids, a);
            auto s = rat::size<ExpSet>(r);
            if (s < best_size)
              {
                best = r;
                best_size = s;
              }
          }
        return best;
      }
    else
      {
        return to_expression_heuristic<Aut, ExpSet>(aut, ids, algo);
      }
  }

  template <Automaton Aut,
            typename ExpSet = expressionset<context_t_of<Aut>>>
  typename ExpSet::value_t
  to_expression(const Aut& a, vcsn::rat::identities ids,
                const std::string& algo)
  {
    static const auto map = getarg<to_expression_heuristic_t>
      {
        "heuristics",
        {
          {"auto",          "best"},
          {"best",          to_expression_heuristic_t::best},
          {"delgado",       to_expression_heuristic_t::delgado},
          {"delgado_label", to_expression_heuristic_t::delgado_label},
          {"naive",         to_expression_heuristic_t::naive}
        }
      };
    return to_expression<Aut, ExpSet>(a, ids, map[algo]);
  }

  /*----------------------------.
  | to_expression(automaton).   |
  `----------------------------*/

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut, typename Identities, typename String>
      expression
      to_expression(const automaton& aut, identities ids,
                    const std::string& algo)
      {
        const auto& a = aut->as<Aut>();
        using context_t = context_t_of<Aut>;
        using expressionset_t = vcsn::expressionset<context_t>;
        auto rs = expressionset_t{a->context(), ids};
        auto res = ::vcsn::to_expression(a, ids, algo);
        return {rs, res};
      }
    }
  }

  /*------------------------.
  | to_expression(label).   |
  `------------------------*/

  namespace dyn
  {
    namespace detail
    {
      template <typename Context, typename Identities, typename Label>
      expression
      to_expression_label(const context& ctx, identities ids,
                          const label& lbl)
      {
        const auto& c = ctx->as<Context>();
        const auto& l = lbl->as<Label>();
        auto rs = vcsn::make_expressionset(c, ids);
        return {rs, rs.atom(l.value())};
      }
    }
  }


  /*-------------------------------.
  | to_expression(letter_class).   |
  `-------------------------------*/

  namespace detail
  {
    template <typename ExpSet>
    auto letter_class_impl(const ExpSet&,
                           const letter_class_t&, bool,
                           std::false_type, std::true_type)
      -> typename ExpSet::value_t
    {
      raise("letter_class: not implemented (is_expressionset)");
    }

    template <typename ExpSet>
    auto letter_class_impl(const ExpSet& rs,
                           const letter_class_t& chars, bool accept,
                           std::false_type, std::false_type)
      -> typename ExpSet::value_t
    {
      auto ls = *rs.labelset();

      using labelset_t = decltype(ls);
      using letter_t = typename labelset_t::letter_t;

      auto ccs = std::set<std::pair<letter_t, letter_t>>{};
      for (const auto& cc: chars)
        {
          std::istringstream i1{cc.first};
          std::istringstream i2{cc.second};
          letter_t l1 = ls.get_letter(i1, false);
          letter_t l2 = ls.get_letter(i2, false);
          ccs.emplace(l1, l2);
        }
      return rs.letter_class(ccs, accept);
    }

    template <typename ExpSet>
    auto letter_class_impl(const ExpSet& rs,
                           const letter_class_t&, bool,
                           std::true_type, std::false_type)
      -> typename ExpSet::value_t
    {
      return rs.one();
    }
  }

  template <typename ExpressionSet>
  typename ExpressionSet::value_t
  to_expression(const ExpressionSet& rs, const letter_class_t& letters,
                bool accept = true)
  {
    using labelset_t = labelset_t_of<ExpressionSet>;
    using is_one_t = std::is_same<labelset_t, vcsn::oneset>;
    using is_expset_t = bool_constant<labelset_t::is_expressionset()>;
    return detail::letter_class_impl(rs, letters, accept,
                                     is_one_t{}, is_expset_t{});
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename Context, typename Identities,
                typename Letters, typename Bool>
      expression
      to_expression_class(const context& ctx, identities ids,
                          const letter_class_t& letters, bool accept)
      {
        const auto& c = ctx->as<Context>();
        auto rs = vcsn::make_expressionset(c, ids);
        return {rs, to_expression(rs, letters, accept)};
      }
    }
  }
} // vcsn::