Vcsn  2.2
Be Rational
complement.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <set>
4 
5 #include <vcsn/algos/copy.hh>
8 #include <vcsn/dyn/expansion.hh>
9 #include <vcsn/misc/raise.hh>
10 #include <vcsn/weightset/fwd.hh> // b
11 
12 namespace vcsn
13 {
14 
15  /*------------------------.
16  | complement(automaton). |
17  `------------------------*/
18 
19  template <Automaton Aut>
20  void
21  complement_here(Aut& aut)
22  {
23  using automaton_t = Aut;
25  "complement: requires free labelset");
27  "complement: requires a deterministic automaton");
28  require(is_complete(aut),
29  "complement: requires a complete automaton");
30 
31  using state_t = state_t_of<automaton_t>;
32 
33  // The final states of aut.
34  auto finals = std::set<state_t>{};
35  for (auto t: final_transitions(aut))
36  finals.insert(aut->src_of(t));
37 
38  // Complement.
39  for (auto s: aut->states())
40  if (has(finals, s))
41  aut->unset_final(s);
42  else
43  aut->set_final(s);
44  }
45 
46  template <Automaton Aut>
47  auto
48  complement(const Aut& aut)
49  -> decltype(copy(aut))
50  {
51  auto res = copy(aut);
52  complement_here(res);
53  return res;
54  }
55 
56  namespace dyn
57  {
58  namespace detail
59  {
61  template <Automaton Aut>
62  automaton
63  complement(const automaton& aut)
64  {
65  const auto& a = aut->as<Aut>();
66  return make_automaton(::vcsn::complement(a));
67  }
68  }
69  }
70 
71  /*-------------------------.
72  | complement(expansion). |
73  `-------------------------*/
74 
75  namespace dyn
76  {
77  namespace detail
78  {
80  template <typename ExpansionSet>
81  expansion
83  {
84  const auto& x = xpn->as<ExpansionSet>();
85  return make_expansion(x.expansionset(),
86  x.expansionset().complement(x.expansion()));
87  }
88  }
89  }
90 
91 
92  /*--------------------------.
93  | complement(expression). |
94  `--------------------------*/
95 
96  namespace dyn
97  {
98  namespace detail
99  {
101  template <typename ExpSet>
102  expression
104  {
105  const auto& e = exp->as<ExpSet>();
106  return make_expression(e.expressionset(),
107  e.expressionset().complement(e.expression()));
108  }
109  }
110  }
111 }
expression complement_expression(const expression &exp)
Bridge (complement).
Definition: complement.hh:103
expansion complement_expansion(const expansion &xpn)
Bridge (complement).
Definition: complement.hh:82
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
std::shared_ptr< const detail::expansion_base > expansion
Definition: expansion.hh:73
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
auto complement(const Aut &aut) -> decltype(copy(aut))
Definition: complement.hh:48
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
bool is_complete(const Aut &aut)
Whether aut is complete.
Definition: is-complete.hh:13
void complement_here(Aut &aut)
Definition: complement.hh:21
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:148
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
expansion make_expansion(const ExpansionSet &ps, const typename ExpansionSet::value_t &expansion)
Definition: expansion.hh:78
expression make_expression(const ExpSet &rs, const typename ExpSet::value_t &r)
Definition: expression.hh:97
automaton complement(const automaton &aut)
Bridge.
Definition: complement.hh:63
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:308