prefix.hh

Go to the documentation of this file.

#pragma once

#include <vcsn/algos/accessible.hh>
#include <vcsn/dyn/automaton.hh> // dyn::make_automaton
#include <vcsn/dyn/fwd.hh>
#include <vcsn/labelset/labelset.hh>

namespace vcsn
{
  /*---------.
  | suffix.  |
  `---------*/

  template <Automaton Aut>
  Aut&
  suffix_here(Aut& aut)
  {
    for (auto s : accessible_states(aut))
      if (s != aut->pre()
          && s != aut->post()
          && !aut->is_initial(s))
        aut->set_initial(s);
    return aut;
  }

  template <Automaton Aut>
  auto
  suffix(const Aut& aut)
    ->decltype(::vcsn::copy(aut))
  {
    auto res = ::vcsn::copy(aut);
    suffix_here(res);
    return res;
  }

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


  /*---------.
  | prefix.  |
  `---------*/

  template <Automaton Aut>
  Aut&
  prefix_here(Aut& aut)
  {
    auto t = transpose(aut);
    suffix_here(t);
    return aut;
  }

  template <Automaton Aut>
  auto
  prefix(const Aut& aut)
    ->decltype(::vcsn::copy(aut))
  {
    auto res = ::vcsn::copy(aut);
    prefix_here(res);
    return res;
  }

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

  /*---------.
  | factor.  |
  `---------*/

  template <Automaton Aut>
  Aut&
  factor_here(Aut& aut)
  {
    return suffix_here(prefix_here(aut));
  }

  template <Automaton Aut>
  auto
  factor(const Aut& aut)
    ->decltype(::vcsn::copy(aut))
  {
    auto res = ::vcsn::copy(aut);
    factor_here(res);
    return res;
  }

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

  /*----------.
  | subword.  |
  `----------*/

  template <Automaton Aut>
  Aut&
  subword_here(Aut& aut)
  {
    const auto one = aut->labelset()->one();

    auto ts = std::vector<transition_t_of<Aut>>{};
    for (auto s : aut->states())
      {
        ts.clear();
        for (auto t : out(aut, s))
          if (!aut->labelset()->is_one(aut->label_of(t)))
            ts.emplace_back(t);
        for (auto t : ts)
          aut->add_transition(s, aut->dst_of(t), one, aut->weight_of(t));
      }

    return aut;
  }

  template <Automaton Aut>
  auto
  subword(const Aut& aut)
    -> decltype(make_nullable_automaton(aut->context()))
  {
    auto res = make_nullable_automaton(aut->context());
    copy_into(aut, res);
    subword_here(res);
    return res;
  }

  namespace dyn
  {
    namespace detail
    {
      template <Automaton Aut>
      automaton
      subword(const automaton& aut)
      {
        const auto& a = aut->as<Aut>();
        return ::vcsn::subword(a);
      }
    }
  }
} // namespace vcsn