Vcsn  2.3
Be Rational
star.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/copy.hh>
6 #include <vcsn/algos/standard.hh> // is_standard
7 #include <vcsn/algos/tags.hh>
9 #include <vcsn/ctx/traits.hh>
10 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
11 #include <vcsn/misc/raise.hh> // require
12 #include <vcsn/misc/vector.hh>
13 
14 namespace vcsn
15 {
16  /*------.
17  | star |
18  `------*/
19 
21  template <Automaton Aut>
22  Aut&
24  {
25  const auto& ws = *res->weightset();
26  const auto& ls = *res->labelset();
27  // Branch all the final states (but initials) to initial states.
28  auto initial = res->new_state();
29  for (auto ti: detail::make_vector(initial_transitions(res)))
30  {
31  res->new_transition(initial, res->dst_of(ti),
32  ls.one(), res->weight_of(ti));
33  res->del_transition(ti);
34  }
35  for (auto tf: detail::make_vector(final_transitions(res)))
36  {
37  res->add_transition(res->src_of(tf), initial,
38  ls.one(), res->weight_of(tf));
39  res->del_transition(tf);
40  }
41  res->set_initial(initial, ws.one());
42  res->set_final(initial, ws.one());
43  return res;
44  }
45 
49  template <Automaton Aut>
50  Aut&
52  {
57  require(is_standard(res), __func__, ": input must be standard");
58 
59  using automaton_t = Aut;
60  using context_t = context_t_of<automaton_t>;
61  using weightset_t = weightset_t_of<context_t>;
62  using weight_t = weight_t_of<context_t>;
63  using state_t = state_t_of<automaton_t>;
64 
65  weightset_t ws(*res->context().weightset());
66 
67  state_t initial = res->dst_of(initial_transitions(res).front());
68  // The "final weight of the initial state", starred.
69  weight_t w = ws.star(res->get_final_weight(initial));
70  // Branch all the final states (but initial) to the successors
71  // of initial.
72  for (auto ti: out(res, initial))
73  {
74  res->lweight(ti, w);
75  for (auto tf: final_transitions(res))
76  if (res->src_of(tf) != initial)
77  // The weight of ti has already been multiplied, on the
78  // left, by w.
79  res->add_transition
80  (res->src_of(tf),
81  res->dst_of(ti),
82  res->label_of(ti),
83  ws.mul(res->weight_of(tf), res->weight_of(ti)));
84  }
85  for (auto tf: final_transitions(res))
86  res->rweight(tf, w);
87  res->set_final(initial, w);
88  return res;
89  }
90 
92  template <Automaton Aut>
93  Aut&
95  {
96  // Cannot use general star_here since it introduces spontaneous
97  // transitions. Standard star_here requires the automaton to be
98  // standard.
99  standard_here(res);
100  star_here(res, standard_tag{});
101  res = determinize(res)->strip();
102  return res;
103  }
104 
106  template <Automaton Aut, typename Tag = general_tag>
107  auto
108  star(const Aut& aut, Tag tag = {})
109  -> decltype(detail::make_join_automaton(tag, aut))
110  {
111  auto res = detail::make_join_automaton(tag, aut);
112  copy_into(aut, res);
113  star_here(res, tag);
114  return res;
115  }
116 
117  namespace dyn
118  {
119  namespace detail
120  {
122  template <Automaton Aut, typename String>
123  automaton
124  star(const automaton& a, const std::string& algo)
125  {
126  const auto& aut = a->as<Aut>();
128  [aut](auto tag)
129  {
130  return automaton(::vcsn::star(aut, tag));
131  },
132  aut);
133  }
134  }
135  }
136 }
Tag for operations on all automata.
Definition: tags.hh:22
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
Tag for operations on standard automata.
Definition: tags.hh:32
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
return res
Definition: multiply.hh:398
bool is_standard(const Aut &a)
Whether a is standard.
Definition: standard.hh:28
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Aut & star_here(Aut &res, general_tag={})
In-place star of an automaton.
Definition: star.hh:23
void standard_here(Aut &aut)
Turn aut into a standard automaton.
Definition: standard.hh:80
Definition: a-star.hh:8
A dyn automaton.
Definition: automaton.hh:17
void copy_into(const AutIn &in, AutOut &out, KeepState keep_state, KeepTrans keep_trans)
Copy selected states and transitions of an automaton.
Definition: copy.hh:267
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
auto make_join_automaton(deterministic_tag, Auts &&...auts) -> decltype(join_automata(std::forward< Auts >(auts)...))
Make an empty automaton which is a supertype of others.
Definition: tags.hh:92
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:145
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
auto dispatch_tags(std::string algo, Operation op, Aut &&...auts)
Dispatch an operation between automata depending on their nature.
Definition: tags.hh:46
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
Tag for operations on deterministic automata.
Definition: tags.hh:19
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:156
auto star(const Aut &aut, Tag tag={}) -> decltype(detail::make_join_automaton(tag, aut))
Star of an automaton.
Definition: star.hh:108
automaton star(const automaton &a, const std::string &algo)
Bridge.
Definition: star.hh:124