automaton.hh

Go to the documentation of this file.

#pragma once

#include <vector>

#include <vcsn/concepts/automaton.hh>
#include <vcsn/ctx/traits.hh> // state_t_of, transition_t_of

namespace vcsn
{

  template <typename Aut>
  using predecessors_t_of = std::vector<transition_t_of<Aut>>;

  template <typename Aut>
  using path_t_of = std::vector<transition_t_of<Aut>>;

  namespace detail
  {

    /*---------.
    | Sizes.   |
    `---------*/

    template <Automaton Aut>
    size_t states_size(const Aut& aut)
    {
      // Cannot be empty.
      return aut->all_states().back() + 1;
    }

    template <Automaton Aut>
    size_t transitions_size(const Aut& aut)
    {
      return (aut->all_transitions().empty()
              ? 0
              : aut->all_transitions().back() + 1);
    }


    /*------------------------.
    | Outgoing transitions.   |
    `------------------------*/

    template <Automaton Aut>
    auto all_out(const Aut& aut, state_t_of<Aut> s)
    {
      return aut->all_out(s);
    }

    template <Automaton Aut, typename Pred>
    auto all_out(const Aut& aut, state_t_of<Aut> s, Pred pred)
    {
      return make_container_filter_range(aut->all_out(s), pred);
    }

    template <Automaton Aut>
    auto out(const Aut& aut, state_t_of<Aut> s)
    {
      return all_out(aut, s,
                     [&aut](transition_t_of<Aut> t)
                     {
                       return aut->dst_of(t) != aut->post();
                     });
    }

    template <Automaton Aut>
    auto out(const Aut& aut, state_t_of<Aut> s, label_t_of<Aut> l)
    {
      return all_out(aut, s,
                     [&aut,l](transition_t_of<Aut> t)
                     {
                       return aut->labelset()->equal(aut->label_of(t), l);
                     });
    }

    /*------------------------.
    | Incoming transitions.   |
    `------------------------*/

    template <Automaton Aut>
    auto all_in(const Aut& aut, state_t_of<Aut> s)
    {
      return aut->all_in(s);
    }

    template <Automaton Aut, typename Pred>
    auto all_in(const Aut& aut, state_t_of<Aut> s, Pred pred)
    {
      return make_container_filter_range(aut->all_in(s), pred);
    }

    template <Automaton Aut>
    auto in(const Aut& aut, state_t_of<Aut> s)
    {
      return all_in(aut, s,
                    [&aut](transition_t_of<Aut> t)
                    {
                      return aut->src_of(t) != aut->pre();
                    });
    }

    template <Automaton Aut>
    auto in(const Aut& aut, state_t_of<Aut> s, label_t_of<Aut> l)
    {
      return all_in(aut, s,
                    [&aut,l](transition_t_of<Aut> t)
                    {
                      return aut->labelset()->equal(aut->label_of(t), l);
                    });
    }


    /*-----------------------.
    | Special transitions.   |
    `-----------------------*/

    template <Automaton Aut>
    auto initial_transitions(const Aut& aut)
      -> decltype(aut->all_out(aut->pre())) // for G++ 5.2
    {
      return aut->all_out(aut->pre());
    }

    template <Automaton Aut>
    auto final_transitions(const Aut& aut)
      -> decltype(aut->all_in(aut->post())) // for G++ 5.2
    {
      return aut->all_in(aut->post());
    }


    template <Automaton Aut>
    auto outin(const Aut& aut, state_t_of<Aut> s, state_t_of<Aut> d)
    {
      return all_out(aut, s,
                     [aut, d](transition_t_of<Aut> t)
                     {
                       return aut->dst_of(t) == d;
                     });
    }

    template <Automaton Aut>
    void del_transition(const Aut& aut, state_t_of<Aut> s, state_t_of<Aut> d)
    {
      // Make a copy of the transition indexes, as the iterators are
      // invalidated by del_transition(t).
      for (auto t: make_vector(outin(aut, s, d)))
        aut->del_transition(t);
    }

    /*---------------.
    | Transitions.   |
    `---------------*/

    template <Automaton Aut>
    auto all_transitions(const Aut& aut)
    {
      return aut->all_transitions();
    }

    template <Automaton Aut, typename Pred>
    auto all_transitions(const Aut& aut, Pred pred)
    {
      return make_container_filter_range(aut->all_transitions(), pred);
    }

    template <Automaton Aut>
    bool is_special(const Aut& aut, transition_t_of<Aut> t)
    {
      return aut->src_of(t) != aut->pre() && aut->dst_of(t) != aut->post();
    }

    template <Automaton Aut>
    struct is_special_t
    {
      bool operator()(transition_t_of<Aut> t)
      {
        return is_special(aut, t);
      }
      const Aut& aut;
    };

    template <Automaton Aut>
    auto transitions(const Aut& aut)
      -> decltype(all_transitions(aut, is_special_t<Aut>{aut})) // for G++ 5.2
    {
      return all_transitions(aut, is_special_t<Aut>{aut});
    }
  }
}