proper.hh

Go to the documentation of this file.

#pragma once

#include <stdexcept>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include <boost/lexical_cast.hpp>
#include <boost/heap/fibonacci_heap.hpp>

#include <vcsn/algos/copy.hh>
#include <vcsn/algos/dot.hh>
#include <vcsn/algos/fwd.hh>
#include <vcsn/algos/is-eps-acyclic.hh>
#include <vcsn/algos/is-proper.hh>
#include <vcsn/algos/is-valid.hh>
#include <vcsn/core/kind.hh>
#include <vcsn/labelset/labelset.hh> // make_proper_context
#include <vcsn/misc/attributes.hh>
#include <vcsn/misc/builtins.hh>
#include <vcsn/misc/direction.hh>
#include <vcsn/misc/star-status.hh>
#include <vcsn/misc/vector.hh> // make_vector

#include <vcsn/algos/epsilon-remover.hh>
#include <vcsn/algos/epsilon-remover-separate.hh>
#include <vcsn/algos/epsilon-remover-distance.hh>

namespace vcsn
{
  namespace detail
  {
    template <typename Aut>
    class properer
    {
      using automaton_t = typename std::remove_cv<Aut>::type;
      using weightset_t = weightset_t_of<automaton_t>;
      using labelset_t = labelset_t_of<automaton_t>;
      using aut_proper_t = fresh_automaton_t_of<automaton_t,
                            detail::proper_context<context_t_of<automaton_t>>>;

    public:
      properer(const automaton_t& aut,
               bool prune = true,
               const std::string& algo = "auto")
        : aut_(aut)
        , prune_(prune)
        , algo_(algo)
      {}

      aut_proper_t operator()()
      {
        return proper_star<weightset_t::star_status()>();
      }

    private:
      aut_proper_t remover_()
      {
        if (algo_ == "auto" || algo_ == "default" || algo_ == "inplace")
          {
            auto a = copy(aut_); // in place
            detail::epsilon_remover<decltype(a)> r(a, prune_);
            return r();
          }
        else if (algo_ == "separate")
          {
            detail::epsilon_remover_separate<automaton_t> r(aut_, prune_);
            return r();
          }
        else if (algo_ == "distance")
          {
            detail::epsilon_remover_distance<automaton_t> r(aut_, prune_);
            return r();
          }
        else
          raise("proper: invalid algorithm: ", algo_);
      }

      template <star_status_t Status>
      vcsn::enable_if_t<Status == star_status_t::TOPS, aut_proper_t>
      proper_star()
      {
        try
          {
            return remover_();
          }
        catch (const std::runtime_error&)
          {
            raise("proper: invalid automaton");
          }
      }

      template <star_status_t Status>
      vcsn::enable_if_t<Status == star_status_t::ABSVAL, aut_proper_t>
      proper_star()
      {
        require(is_valid(aut_), "proper: invalid automaton");
        return remover_();
      }

      template <star_status_t Status>
      vcsn::enable_if_t<Status == star_status_t::STARRABLE, aut_proper_t>
      proper_star()
      {
        return remover_();
      }

      template <star_status_t Status>
      vcsn::enable_if_t<Status == star_status_t::NON_STARRABLE, aut_proper_t>
      proper_star()
      {
        require(is_valid(aut_), "proper: invalid automaton");
        return remover_();
      }

      automaton_t aut_;
      bool prune_;
      const std::string& algo_;
    };

    template <typename Aut>
    auto make_properer(Aut aut,
                       bool prune = true,
                       const std::string& algo = "auto")
    {
      return properer<Aut>(aut, prune, algo);
    }
  }

  /*---------.
  | proper.  |
  `---------*/

  template <typename Aut>
  auto
  proper(const Aut& aut, direction dir = direction::backward,
         bool prune = true, const std::string& algo = "auto")
    -> fresh_automaton_t_of<Aut,
                            detail::proper_context<context_t_of<Aut>>>
  {
    switch (dir)
      {
      case direction::backward:
        return detail::make_properer(aut, prune, algo)();
      case direction::forward:
        return transpose(proper(transpose(aut),
                                direction::backward, prune, algo));
      }
    BUILTIN_UNREACHABLE();
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename Aut, typename Dir, typename Bool, typename String>
      automaton proper(const automaton& aut, direction dir, bool prune,
                       const std::string& algo)
      {
        const auto& a = aut->as<Aut>();
        return make_automaton(::vcsn::proper(a, dir, prune, algo));
      }
    }
  }
} // namespace vcsn