Vcsn  2.3
Be Rational
filter.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm> // std::max
4 
5 #include <boost/range/irange.hpp>
6 #include <boost/optional.hpp>
7 
8 #include <vcsn/algos/copy.hh>
10 #include <vcsn/core/automaton.hh> // all_transitions
11 #include <vcsn/dyn/fwd.hh>
12 #include <vcsn/misc/crange.hh>
14 #include <vcsn/misc/sparse-set.hh>
15 #include <vcsn/misc/vector.hh>
16 #include <vcsn/misc/static-if.hh>
17 
18 namespace vcsn
19 {
20  namespace detail
21  {
23  template <typename Container, bool Has = false>
25  {
26  public:
27  template <typename... Args>
28  optional_container(Args&&...)
29  {}
30  };
31 
32  template <typename Container>
33  class optional_container<Container, true>
34  {
35  public:
36  template <typename... Args>
37  optional_container(Args&&... args)
38  : cont_(std::forward<Args>(args)...)
39  {}
40  protected:
41  Container cont_;
42  };
43 
47  template <Automaton Aut, bool Trans = false>
49  : public automaton_decorator<Aut>
50  , public optional_container<dynamic_bitset, Trans>
51  {
52  public:
53  using automaton_t = Aut;
59 
63 
64  using tr_cont_t = std::vector<transition_t>;
65 
66  using super_t::pre;
67  using super_t::post;
68  using super_t::src_of;
69  using super_t::dst_of;
70 
72  const boost::optional<states_t>& ss = {},
73  const boost::optional<transitions_t>& ts = {})
74  : super_t(input)
76  , ss_(ss ? *ss : states_t(states_size(input)))
77  {
78  ss_.set(input->pre());
79  ss_.set(input->post());
80  }
81 
83  static symbol sname()
84  {
85  static auto res = symbol{"filter_automaton<"
87  return res;
88  }
89 
90  std::ostream& print_set(std::ostream& o, format fmt = {}) const
91  {
92  o << "filter_automaton<";
93  aut_->print_set(o, fmt);
94  return o << '>';
95  }
96 
97  bool state_has_name(state_t s) const
98  {
99  assert(has(ss_, s));
100  return aut_->state_has_name(s);
101  }
102 
103  bool has_state(state_t s) const
104  {
105  return has(ss_, s) && aut_->has_state(s);
106  }
107 
108  using super_t::has_transition;
109 
110  template <bool U = Trans>
111  std::enable_if_t<U, bool>
112  has_transition(transition_t t) const
113  {
114  return has(this->cont_, t) && aut_->has_transition(t);
115  }
116 
117  template <bool U = Trans>
118  std::enable_if_t<!U, bool>
119  has_transition(transition_t t) const
120  {
121  return aut_->has_transition(t);
122  }
123 
124  std::ostream& print_state_name(state_t s, std::ostream& o,
125  format fmt = {},
126  bool delimit = false) const
127  {
128  assert(has(ss_, s));
129  return aut_->print_state_name(s, o, fmt, delimit);
130  }
131 
132  size_t num_states() const
133  {
134  return states().size();
135  }
136 
137  size_t num_all_states() const
138  {
139  return all_states().size();
140  }
141 
142  template <typename Pred>
143  auto all_states(Pred pred) const
144  {
145  return aut_->all_states([this, pred](state_t s)
146  {
147  return pred(s) && has(ss_, s);
148  });
149  }
150 
151  auto all_states() const
152  {
153  return all_states([](state_t) { return true; });
154  }
155 
156  auto states() const
157  {
158  return all_states([this](state_t s)
159  {
160  // When transposing post() < pre().
161  return std::max(pre(), post()) < s;
162  });
163  }
164 
167  auto all_transitions() const
168  {
169  return vcsn::detail::all_transitions
170  (aut_,
171  [this](transition_t t)
172  {
173  return has_transition(t)
174  && has(ss_, aut_->src_of(t))
175  && has(ss_, aut_->dst_of(t));
176  });
177  }
178 
180  auto all_out(state_t s) const
181  {
182  return vcsn::detail::all_out(aut_, s,
183  [this](transition_t t)
184  {
185  return has_transition(t)
186  && has(ss_, aut_->dst_of(t));
187  });
188  }
189 
191  auto all_in(state_t s) const
192  {
193  return vcsn::detail::all_in(aut_, s,
194  [this](transition_t t)
195  {
196  return has_transition(t)
197  && has(ss_, aut_->src_of(t));
198  });
199  }
200 
201  void
202  hide_state(state_t s)
203  {
204  if (s < ss_.size())
205  ss_.reset(s);
206  }
207 
210  template <bool U = Trans>
211  std::enable_if_t<U, void>
212  hide_transition(transition_t t)
213  {
214  if (t < optional_container_t::cont_.size())
215  optional_container_t::cont_.reset(t);
216  }
217 
219  void
220  unhide_state(state_t s)
221  {
222  if (s < ss_.size())
223  ss_.set(s);
224  }
225 
228  template <bool U = Trans>
229  std::enable_if_t<U, void>
230  unhide_transition(transition_t t)
231  {
232  if (t < optional_container_t::cont_.size())
233  optional_container_t::cont_.set(t);
234  }
235 
239  void
240  hide_all_states()
241  {
242  ss_.reset();
243  ss_.set(aut_->pre());
244  ss_.set(aut_->post());
245  }
246 
250  void
251  unhide_all_states()
252  {
253  ss_.set();
254  }
255 
256  template <bool U = Trans>
257  std::enable_if_t<U, void>
258  unhide_all_transition()
259  {
260  optional_container_t::cont_.set();
261  }
262 
263  template <bool U = Trans>
264  std::enable_if_t<U, void>
265  hide_all_transition()
266  {
267  optional_container_t::cont_.reset();
268  }
269 
270  fresh_automaton_t_of<automaton_t>
271  strip() const
272  {
273  auto state_filter = [this](state_t_of<automaton_t> s)
274  {
275  return has(this->ss_, s);
276  };
277  auto transition_filter = [this](transition_t_of<automaton_t> t)
278  {
279  return this->has_transition(t);
280  };
281  return ::vcsn::copy(aut_, state_filter, transition_filter);
282  }
283 
284  protected:
286  using super_t::aut_;
287 
288  private:
290  states_t ss_;
291  };
292  }
293 
294  template <Automaton Aut, bool Trans = false>
295  using filter_automaton =
296  std::shared_ptr<detail::filter_automaton_impl<Aut, Trans>>;
297 
299  template <Automaton Aut, bool Trans = false>
300  filter_automaton<Aut, Trans>
301  filter(const Aut& aut,
302  boost::optional<dynamic_bitset> ss = {},
303  boost::optional<dynamic_bitset> ts = {})
304  {
305  return make_shared_ptr<filter_automaton<Aut, Trans>>(aut, ss, ts);
306  }
307 
308  template <Automaton Aut>
309  filter_automaton<Aut>
310  filter(const Aut& aut, const std::unordered_set<state_t_of<Aut>>& ss)
311  {
312  return filter(aut, make_dynamic_bitset(ss, states_size(aut)));
313  }
314 
315  namespace dyn
316  {
317  namespace detail
318  {
320  template <Automaton Aut, typename Unsigneds>
321  automaton
322  filter(const automaton& aut, const std::vector<unsigned>& states)
323  {
324  const auto& a = aut->as<Aut>();
325  // FIXME: This is a problem for lazy automaton.
326  auto size = states_size(a);
327  auto ss = dynamic_bitset(size);
328  for (auto s: states)
329  if (s + 2 < size)
330  ss.set(s + 2);
331  return ::vcsn::filter(a, ss);
332  }
333  }
334  }
335 }
Enables or not the presence of a container in a class.
Definition: filter.hh:24
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
STL namespace.
boost::dynamic_bitset<> dynamic_bitset
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
symbol sname()
Definition: name.hh:65
auto src_of(Args &&...args) const -> decltype(aut_-> src_of(std::forward< Args >(args)...))
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:19
Aggregate an automaton, and forward calls to it.
auto dst_of(Args &&...args) const -> decltype(aut_-> dst_of(std::forward< Args >(args)...))
transition_t_of< automaton_t > transition_t
Definition: filter.hh:57
size_t transitions_size(const Aut &aut)
The largest transition number, plus one.
Definition: automaton.hh:29
Looking downstream.
return res
Definition: multiply.hh:398
states_t ss_
The states we keep.
Definition: filter.hh:290
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
static symbol sname()
Static name.
Definition: filter.hh:83
Hide some states of an automaton.
Definition: filter.hh:48
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
state_t_of< automaton_t > state_t
Definition: filter.hh:56
An input/output format for valuesets.
Definition: format.hh:13
automaton_decorator< automaton_t > super_t
Definition: filter.hh:55
filter_automaton_impl(const automaton_t &input, const boost::optional< states_t > &ss={}, const boost::optional< transitions_t > &ts={})
Definition: filter.hh:71
optional_container< transitions_t, Trans > optional_container_t
Definition: filter.hh:62
label_t_of< automaton_t > label_t
Definition: filter.hh:58
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: filter.hh:90
automaton_t aut_
The wrapped automaton, possibly const.
std::vector< transition_t > tr_cont_t
Definition: filter.hh:64