Vcsn  2.3
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/value.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);
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>();
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 {x.valueset(), x.valueset().complement(x.value())};
86  }
87  }
88  }
89 
90 
91  /*--------------------------.
92  | complement(expression). |
93  `--------------------------*/
94 
95  namespace dyn
96  {
97  namespace detail
98  {
100  template <typename ExpSet>
101  expression
103  {
104  const auto& e = exp->as<ExpSet>();
105  return {e.valueset(),
106  e.valueset().complement(e.value())};
107  }
108  }
109  }
110 }
bool is_complete(const Aut &aut)
Whether aut is complete.
Definition: is-complete.hh:13
void complement_here(Aut &aut)
Definition: complement.hh:21
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
A dyn Value/ValueSet.
Definition: fwd.hh:23
return res
Definition: multiply.hh:398
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
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
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:322
Definition: a-star.hh:8
A dyn automaton.
Definition: automaton.hh:17
expansion complement_expansion(const expansion &xpn)
Bridge (complement).
Definition: complement.hh:82
value_impl< detail::expansion_tag > expansion
Definition: fwd.hh:24
automaton complement(const automaton &aut)
Bridge.
Definition: complement.hh:63
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
expression complement_expression(const expression &exp)
Bridge (complement).
Definition: complement.hh:102
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:156
auto complement(const Aut &aut) -> decltype(copy(aut))
Definition: complement.hh:48