delay-automaton.hh

Go to the documentation of this file.

#pragma once

#include <stack>
#include <vector>

#include <boost/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>

#include <vcsn/algos/fwd.hh>
#include <vcsn/ctx/context.hh>
#include <vcsn/dyn/automaton.hh> // dyn::make_automaton
#include <vcsn/misc/bimap.hh>
#include <vcsn/misc/pair.hh> // hash
#include <vcsn/misc/unordered_map.hh> // has

namespace vcsn
{
  namespace detail
  {

    template <Automaton Aut>
    class delay_automaton_impl
      : public automaton_decorator<fresh_automaton_t_of<Aut>>
    {
    public:
      using automaton_t = Aut;
      using super_t = automaton_decorator<fresh_automaton_t_of<automaton_t>>;
      using context_t = context_t_of<super_t>;
      using labelset_t = labelset_t_of<super_t>;
      using label_t = label_t_of<super_t>;
      using weight_t = weight_t_of<super_t>;
      using state_t = state_t_of<super_t>;

      template <std::size_t... I>
      using seq = vcsn::detail::index_sequence<I...>;

      static constexpr size_t number_of_tapes = labelset_t_of<Aut>::size();

      using index_t = detail::make_index_sequence<number_of_tapes>;

      static constexpr index_t indices = {};

      using delay_t = std::array<size_t, number_of_tapes>;

      using state_name_t = std::pair<state_t, delay_t>;

      using bimap_t =
        boost::bimap<boost::bimaps::unordered_set_of<state_name_t>,
                     boost::bimaps::unordered_set_of<state_t>>;
      using map_t = typename bimap_t::left_map;
      using origins_t = typename bimap_t::right_map;

      template <size_t I>
      using tape_labelset_t = typename labelset_t::template valueset_t<I>;

      delay_automaton_impl(const automaton_t& aut)
        : super_t(aut->context())
        , aut_(aut)
      {
        map_().insert({{this->pre(), delay_t{}}, aut->pre()});
        map_().insert({{this->post(), delay_t{}}, aut->post()});
      }

      static symbol sname()
      {
        static auto res = symbol{"delay_automaton<"
                          + automaton_t::element_type::sname() + '>'};
        return res;
      }

      std::ostream& print_set(std::ostream& o, format fmt = {}) const
      {
        o << "delay_automaton<";
        super_t::print_set(o, fmt);
        return o << '>';
      }

      state_t state(const state_name_t& r)
      {
        if (r.first == aut_->post())
          return this->post();
        state_t res;
        auto i = map_().find(r);
        if (i == std::end(map_()))
          {
            res = super_t::new_state();
            // Emplace is not available because of the internals of bimap
            map_().insert({r, res});
            todo_.push(r);
          }
        else
          res = i->second;
        return res;
      }

      using super_t::new_transition;

      void
      new_transition(const state_name_t& src, const state_name_t& dst,
                     const label_t& l, const weight_t& w)
      {
        super_t::new_transition(state(src), state(dst), l, w);
      }

      bool state_has_name(state_t s) const
      {
        return has(origins(), s);
      }

      std::ostream&
      print_state_name(state_t s, std::ostream& o,
                       format fmt = {},
                       bool = false) const
      {
        auto ns = origins().at(s);
        aut_->print_state_name(ns.first, o, fmt, true);
        o << ":(";
        auto a = ns.second;
        for (int i = 0; i < a.size() - 1; i++)
          o << a[i] << ',';
        if (a.size())
          o << a[a.size() - 1];
        o << ')';
        return o;
      }

      delay_t delay_of(state_t s)
      {
        auto i = origins().find(s);
        if (i == std::end(origins()))
          return {};
        else
          return i->second.second;
      }

      const origins_t&
      origins() const
      {
        return bimap_.right;
      }

      map_t&
      map_()
      {
        return bimap_.left;
      }

      std::stack<state_name_t, std::vector<state_name_t>> todo_;
      bimap_t bimap_;
      automaton_t aut_;
    };

    template <Automaton Aut>
    delay_automaton<Aut>
    make_delay_automaton(const Aut& aut)
    {
      auto s = synchronize_checker<Aut>{aut};
      return s.make_delay_automaton();
    }
  }


  /*------------------.
  | delay_automaton.  |
  `------------------*/

  template <Automaton Aut>
  auto
  make_delay_automaton(const Aut& aut)
    -> decltype(detail::make_delay_automaton(aut))
  {
    return detail::make_delay_automaton(aut);
  }

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut>
      automaton delay_automaton(const automaton& aut)
      {
        return make_automaton(vcsn::make_delay_automaton(aut->as<Aut>()));
      }
    }
  }
}