copy.hh

Go to the documentation of this file.

#pragma once

#include <unordered_map>

#include <vcsn/algos/fwd.hh> // focus_automaton.
#include <vcsn/core/automaton-decorator.hh>
#include <vcsn/core/automaton.hh>
#include <vcsn/core/fwd.hh>
#include <vcsn/core/mutable-automaton.hh>
#include <vcsn/core/rat/copy.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/context.hh>
#include <vcsn/dyn/types.hh>
#include <vcsn/dyn/value.hh>
#include <vcsn/misc/attributes.hh>
#include <vcsn/misc/set.hh>
#include <vcsn/misc/unordered_set.hh>

namespace vcsn
{

  namespace detail
  {
    template <Automaton Aut>
    struct real_context_impl;

    template <Automaton Aut>
    auto
    real_context(const Aut& aut)
      -> decltype(real_context_impl<Aut>::context(aut));

    template <Automaton Aut>
    struct real_context_impl
    {
      static auto context(const Aut& aut)
        -> decltype(aut->context())
      {
        return aut->context();
      }
    };

    template <std::size_t Tape, Automaton Aut>
    struct real_context_impl<focus_automaton<Tape, Aut>>
    {
      static auto context(const focus_automaton<Tape, Aut>& aut)
        -> decltype(aut->full_context())
      {
        return aut->full_context();
      }
    };

    //
    // FIXME: try to recurse on all automaton decorator types without
    // listing them.
    template <Automaton Aut>
    struct real_context_impl<automaton_decorator<Aut>>
    {
      static auto context(const automaton_decorator<Aut>& aut)
        -> decltype(real_context(aut->strip()))
      {
        return real_context(aut->strip());
      }
    };

    template <Automaton Aut>
    auto
    real_context(const Aut& aut)
      -> decltype(real_context_impl<Aut>::context(aut))
    {
      return real_context_impl<Aut>::context(aut);
    }
  }

  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>>
  AutOut
  make_fresh_automaton(const AutIn& model)
  {
    // FIXME: here, we need a means to convert the given input context
    // (e.g. letter -> B) into the destination one (e.g., letter ->
    // Q).  The automaton constructor wants the exact context type.
    return make_shared_ptr<AutOut>(detail::real_context(model));
  }


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

  namespace detail
  {
    template <Automaton AutIn, Automaton AutOut = AutIn>
    class copier
    {
    public:
      using in_automaton_t = AutIn;
      using out_automaton_t = AutOut;

      using in_state_t = state_t_of<in_automaton_t>;
      using out_state_t = state_t_of<out_automaton_t>;
      using state_map_t = std::unordered_map<in_state_t, out_state_t>;

    private:
      in_automaton_t in_;
      out_automaton_t out_;
      bool safe_ = true;
      state_map_t out_state_;

    public:
      copier(const in_automaton_t& in, out_automaton_t& out,
             bool safe = true)
        : in_(in)
        , out_(out)
        , safe_(safe)
        , out_state_{{in_->pre(),  out_->pre()},
                     {in_->post(), out_->post()}}
      {}

      template <typename KeepState, typename KeepTrans>
      void operator()(KeepState keep_state, KeepTrans keep_trans)
      {
        // Copy the states.  We cannot iterate on the transitions
        // only, as we would lose the states without transitions.  And
        // this way, we keep the states in the same order.
        for (auto s: in_->states())
          if (keep_state(s))
            out_state_[s] = out_->new_state();

        for (auto t : all_transitions(in_))
          if (keep_trans(t))
            {
              auto src = out_state_.find(in_->src_of(t));
              auto dst = out_state_.find(in_->dst_of(t));
              if (src != out_state_.end() && dst != out_state_.end())
                {
                  if (safe_)
                    out_->new_transition_copy(src->second, dst->second,
                                              in_, t);
                  else
                    out_->add_transition_copy(src->second, dst->second,
                                              in_, t);
                }
            }
      }

      template <typename Transitions>
      auto operator()(const Transitions& ts)
        -> decltype(ts[0] == in_->null_transition(), void())
      {
        for (auto t : ts)
          operator()(t);
      }

      void operator()(const transition_t_of<in_automaton_t>& t)
      {
        auto src = state(in_->src_of(t));
        auto dst = state(in_->dst_of(t));
        if (safe_)
          out_->new_transition_copy(src, dst, in_, t);
        else
          out_->add_transition_copy(src, dst, in_, t);
      }

      void operator()()
      {
        operator()([](state_t_of<in_automaton_t>) { return true; },
                   [](transition_t_of<in_automaton_t>) { return true; });
      }

      const state_map_t& state_map() const
      {
        return out_state_;
      }

      state_map_t& state_map()
      {
        return out_state_;
      }

    private:
      out_state_t state(const in_state_t& s)
      {
        out_state_t res;
        auto i = out_state_.find(s);
        if (i == std::end(out_state_))
          res = out_state_.emplace(s, out_->new_state()).first->second;
        else
          res = i->second;
        return res;
      }
    };
  }


  template <Automaton AutIn, Automaton AutOut>
  detail::copier<AutIn, AutOut>
  make_copier(const AutIn& in, AutOut& out, bool safe = true)
  {
    return {in, out, safe};
  }


  template <Automaton AutIn, Automaton AutOut,
            typename KeepState, typename KeepTrans>
  void
  copy_into(const AutIn& in, AutOut& out,
            KeepState keep_state, KeepTrans keep_trans)
  {
    auto copy = make_copier(in, out);
    copy(keep_state, keep_trans);
  }

  template <Automaton AutIn, Automaton AutOut, typename KeepState>
  void
  copy_into(const AutIn& in, AutOut& out, KeepState keep_state)
  {
    return copy_into(in, out, keep_state,
                     [](transition_t_of<AutIn>) { return true; });
  }


  template <Automaton AutIn, Automaton AutOut>
  void
  copy_into(const AutIn& in, AutOut& out)
  {
    return copy_into(in, out,
                     [](state_t_of<AutIn>) { return true; },
                     [](transition_t_of<AutIn>) { return true; });
  }


  template <Automaton AutIn, Automaton AutOut>
  void
  copy_into(const AutIn& in, AutOut& out, bool safe)
  {
    auto copy = make_copier(in, out, safe);
    copy([](state_t_of<AutIn>) { return true; },
         [](transition_t_of<AutIn>) { return true; });
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>,
            typename KeepState, typename KeepTrans>
  auto
  copy(const AutIn& input, KeepState keep_state, KeepTrans keep_trans)
    -> decltype(keep_state(input->null_state()),
                keep_trans(input->null_transition()),
                make_fresh_automaton<AutIn, AutOut>(input))
  {
    auto res = make_fresh_automaton<AutIn, AutOut>(input);
    ::vcsn::copy_into(input, res, keep_state, keep_trans);
    return res;
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>,
            typename KeepState>
  auto
  copy(const AutIn& input, KeepState keep_state)
    -> decltype(keep_state(input->null_state()),
                make_fresh_automaton<AutIn, AutOut>(input))
  {
    return ::vcsn::copy<AutIn, AutOut>(
             input,
             keep_state,
             [](transition_t_of<AutIn>) { return true; }
    );
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>>
  AutOut
  copy(const AutIn& input)
  {
    return ::vcsn::copy<AutIn, AutOut>(
             input,
             [](state_t_of<AutIn>) { return true; },
             [](transition_t_of<AutIn>) { return true; }
    );
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>,
            typename States>
  auto
  copy(const AutIn& input, const States& ss)
    -> decltype(*ss.begin() == input->null_state(),
                make_fresh_automaton<AutIn, AutOut>(input))
  {
    return ::vcsn::copy<AutIn, AutOut>
      (input,
       [&ss](state_t_of<AutIn> s) { return has(ss, s); });
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>,
            typename States, typename Trans>
  auto
  copy(const AutIn& input, const States& ss, const Trans& ts)
    -> decltype(*ss.begin() == input->null_state(),
                *ts.begin() == input->null_transition(),
                make_fresh_automaton<AutIn, AutOut>(input))
  {
    return ::vcsn::copy<AutIn, AutOut>
      (input,
       [&ss](state_t_of<AutIn> s)      { return has(ss, s); },
       [&ts](transition_t_of<AutIn> t) { return has(ts, t); });
  }


  template <Automaton AutIn,
            Automaton AutOut = fresh_automaton_t_of<AutIn>,
            typename Transitions>
  auto
  copy(const AutIn& input, const Transitions& ts)
    -> decltype(*ts.begin() == input->null_transition(),
                make_fresh_automaton<AutIn, AutOut>(input))
  {
    auto res = make_fresh_automaton<AutIn, AutOut>(input);
    auto copy = make_copier(input, res);
    copy(ts);
    return res;
  }


  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut, typename Ctx>
      automaton
      copy_convert(const automaton& aut, const context& ctx)
      {
        const auto& a = aut->as<Aut>();
        const auto& c = ctx->as<Ctx>();
        auto res = make_mutable_automaton(c);
        ::vcsn::copy_into(a, res);
        return res;
      }

      template <Automaton Aut>
      automaton
      copy(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return ::vcsn::copy(a);
      }
    }
  }

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

  namespace dyn
  {
    namespace detail
    {
      template <typename ExpSet, typename Context, typename Identities>
      expression
      copy_expression(const expression& exp,
                      const context& ctx, identities ids)
      {
        const auto& r = exp->as<ExpSet>();
        const auto& c = ctx->as<Context>();
        const auto& rs = make_expressionset(c, ids);

        return {rs, ::vcsn::rat::copy(r.valueset(),
                                      rs,
                                      r.value())};
      }
    }
  }
} // namespace vcsn