Vcsn  2.3
Be Rational
epsilon-remover-lazy.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/ctx/traits.hh>
6 #include <vcsn/core/automaton.hh>
8 #include <vcsn/misc/symbol.hh>
9 #include <vcsn/misc/raise.hh>
10 
11 namespace vcsn
12 {
13  namespace detail
14  {
29  template <Automaton Aut,
30  bool has_one = labelset_t_of<Aut>::has_one()>
32  : public automaton_decorator<fresh_automaton_t_of<Aut,
33  detail::proper_context<context_t_of<Aut>>>>
34  {
35  public:
36  using in_automaton_t = Aut;
38 
41 
46 
48 
49  static symbol sname()
50  {
51  static auto res = symbol{"lazy_proper_automaton<"
53  + '>'};
54  return res;
55  }
56 
57  std::ostream& print_set(std::ostream& o, format fmt) const
58  {
59  o << "lazy_proper_automaton<";
60  this->aut_->print_set(o, fmt);
61  return o << '>';
62  }
63 
67  lazy_proper_automaton_impl(const in_automaton_t& a, bool prune = true)
68  : super_t(make_proper_context(a->context()))
69  , remover_(transpose(a), prune)
70  {
71  this->aut_ = transpose(remover_.get_proper());
72  proper_states_.emplace(this->post()); // post is already proper
73  known_states_.emplace(this->pre()); // pre is always there
74  known_states_.emplace(this->post()); // post is always there
75  }
76 
78  bool state_has_spontaneous_out(state_t s) const
79  {
80  // We work on the transpose automaton, in and out are reversed
81  return remover_.state_has_spontaneous_in(s);
82  }
83 
90  void complete_(state_t s) const
91  {
92  auto& self = const_cast<self_t&>(*this);
93 
94  bool has_removed = true;
95  while (has_removed)
96  {
97  auto ts = vcsn::detail::all_out(this->aut_, s);
98  auto todo = std::vector<state_t>(ts.size());
99  std::transform(begin(ts), end(ts), begin(todo),
100  [this](auto t){ return this->aut_->dst_of(t); });
101  has_removed = false;
102  for (auto succ : todo)
103  if (state_has_spontaneous_out(succ))
104  {
105  self.remover_.remover_on(succ);
106  has_removed = true;
107  }
108  }
109 
110  for (auto t : vcsn::detail::all_out(this->aut_, s))
111  self.known_states_.emplace(this->aut_->dst_of(t));
112  self.proper_states_.emplace(s);
113  }
114 
116  auto all_out(state_t s) const
117  -> decltype(vcsn::detail::all_out(this->aut_, s))
118  {
119  if (is_lazy(s))
120  complete_(s);
121  return vcsn::detail::all_out(this->aut_, s);
122  }
123 
124  bool is_lazy(state_t s) const
125  {
126  return !has(proper_states_, s);
127  }
128 
131  auto all_states() const
132  {
133  return all_states([](state_t){ return true; });
134  }
135 
138  template <typename Pred>
139  auto all_states(Pred pred) const
140  {
141  return this->aut_->all_states(
142  [this, pred](state_t s)
143  {
144  return pred(s) && has(known_states_, s);
145  });
146  }
147 
150  auto states() const
151  {
152  return all_states(
153  [this](state_t s)
154  {
155  return s != this->aut_->pre() && s != this->aut_->post();
156  });
157  }
158 
159  private:
160  epsilon_remover_separate<transpose_in_automaton_t> remover_;
161 
163  std::unordered_set<state_t> proper_states_;
164 
167  std::unordered_set<state_t> known_states_;
168  };
169 
172  template <Automaton Aut>
173  class lazy_proper_automaton_impl<Aut, false>
174  : public automaton_decorator<Aut>
175  {
176  public:
177  using automaton_t = Aut;
178  using super_t = automaton_decorator<automaton_t>;
179  using state_t = state_t_of<automaton_t>;
180 
181  static symbol sname()
182  {
183  static auto res = symbol{"lazy_proper_automaton<"
184  + automaton_t::element_type::sname()
185  + '>'};
186  return res;
187  }
188 
189  std::ostream& print_set(std::ostream& o, format fmt) const
190  {
191  o << "lazy_proper_automaton<";
192  this->aut_->print_set(o, fmt);
193  return o << '>';
194  }
195 
196  lazy_proper_automaton_impl(const automaton_t& a, bool)
197  : super_t(a)
198  {}
199  };
200  }
201 
202  template <Automaton Aut>
203  using lazy_proper_automaton
204  = std::shared_ptr<detail::lazy_proper_automaton_impl<Aut>>;
205 }
#define Automaton
Definition: automaton.hh:23
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
context_t_of< in_automaton_t > in_context_t
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
symbol sname()
Definition: name.hh:65
Aggregate an automaton, and forward calls to it.
fresh_automaton_t_of< Aut, context_t > automaton_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
return res
Definition: multiply.hh:398
lazy_proper_automaton_impl(const in_automaton_t &a, bool prune=true)
We cannot initialize super_t with the input automaton, we have to call remover_() first with the tran...
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Definition: a-star.hh:8
std::shared_ptr< detail::transpose_automaton_impl< Aut >> transpose_automaton
An automaton wrapper that presents the transposed automaton.
Definition: fwd.hh:108
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:82
transpose_automaton< in_automaton_t > transpose_in_automaton_t
An input/output format for valuesets.
Definition: format.hh:13
Build a "lazy proper" automaton from the input with nullable labels.
transition_t_of< automaton_t > transition_t
std::ostream & print_set(std::ostream &o, format fmt) const