Vcsn  2.3
Be Rational
letterize.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iterator>
4 
5 #include <vcsn/algos/proper.hh>
7 #include <vcsn/ctx/context.hh>
8 #include <vcsn/ctx/traits.hh> // context_t_of
9 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
10 #include <vcsn/labelset/labelset.hh> // detail::make_letterized
11 
12 namespace vcsn
13 {
14 
15  /*------------------------.
16  | letterize(automaton). |
17  `------------------------*/
18  namespace detail
19  {
21  template <Automaton AutIn, Automaton AutOut>
22  class letterizer
23  {
24  public:
25  using in_automaton_t = AutIn;
29  using in_label_t = typename in_labelset_t::value_t;
31 
32  using out_automaton_t = AutOut;
36  using out_label_t = typename out_labelset_t::value_t;
38 
39  // map in_state_t -> out_state_t
40  using map_t = std::vector<out_state_t>;
41 
42  letterizer(const in_automaton_t& in_aut, const out_labelset_t& ls)
43  : in_aut_(in_aut)
44  , out_aut_(make_mutable_automaton(out_ctx_t{ls, *in_aut->weightset()}))
45  , state_map_(states_size(in_aut))
46  {}
47 
49  {
50  auto in_ls = in_aut_->labelset();
51  auto out_ws = out_aut_->weightset();
52  // Copy the states, and setup the map
53  state_map_[in_aut_->pre()] = out_aut_->pre();
54  state_map_[in_aut_->post()] = out_aut_->post();
55  for (auto st : in_aut_->states())
56  state_map_[st] = out_aut_->new_state();
57 
58  for (auto st : in_aut_->all_states())
59  for (auto tr : all_out(in_aut_, st))
60  {
61  auto letters = in_ls->letters_of_padded(in_aut_->label_of(tr),
63  auto it = letters.begin();
64  if (it != letters.end())
65  {
66  auto src = state_map_[st];
67  auto dst = std::next(it) != letters.end()
68  ? out_aut_->new_state()
69  : state_map_[in_aut_->dst_of(tr)];
70  out_aut_->new_transition(src, dst,
71  *it, in_aut_->weight_of(tr));
72  src = dst;
73  for (++it; it != letters.end(); ++it)
74  {
75  dst = std::next(it) == letters.end()
76  ? state_map_[in_aut_->dst_of(tr)]
77  : out_aut_->new_state();
78  out_aut_->new_transition(src, dst, *it, out_ws->one());
79  src = dst;
80  }
81  }
82  else
83  out_aut_->new_transition(state_map_[st],
84  state_map_[in_aut_->dst_of(tr)],
86  in_aut_->weight_of(tr));
87  }
88 
89  return std::move(out_aut_);
90  }
91 
92  protected:
96  };
97 
98 
99  template <Automaton Aut>
101 
103  template <Automaton Aut>
104  std::enable_if_t<!is_letterized_t<labelset_t_of<Aut>>{},
106  letterize(const Aut& aut)
107  {
109  auto lt = letterizer<Aut, res_t>{aut,
110  make_letterized(*aut->labelset())};
111  return lt.letterize();
112  }
113 
115  template <Automaton Aut>
116  std::enable_if_t<is_letterized_t<labelset_t_of<Aut>>{},
117  const Aut&>
118  letterize(const Aut& aut)
119  {
120  return aut;
121  }
122  }
123 
124  /*------------------------.
125  | letterize(automaton). |
126  `------------------------*/
127 
132  template <Automaton Aut>
133  auto
134  letterize(const Aut& aut)
135  -> decltype(detail::letterize(aut))
136  {
137  return detail::letterize(aut);
138  }
139 
140  namespace dyn
141  {
142  namespace detail
143  {
145  template <Automaton Aut>
147  {
148  return ::vcsn::letterize(aut->as<Aut>());
149  }
150  }
151  }
152 
153  /*----------------------------.
154  | is_letterized(automaton). |
155  `----------------------------*/
156 
157  namespace detail
158  {
159  template <Automaton Aut>
160  std::enable_if_t<!is_letterized_t<labelset_t_of<Aut>>{}, bool>
161  is_letterized(const Aut& aut)
162  {
163  auto ls = aut->labelset();
164  for (auto t : transitions(aut))
165  {
166  auto it = ls->letters_of_padded(aut->label_of(t),
168  // size is not 0 or 1, then it's a word
169  // we can't use size, as it's not defined for zip_iterators
170  if (it.begin() != it.end() && ++(it.begin()) != it.end())
171  return false;
172  }
173  return true;
174  }
175 
176  template <Automaton Aut>
177  std::enable_if_t<is_letterized_t<labelset_t_of<Aut>>{}, bool>
178  is_letterized(const Aut&)
179  {
180  return true;
181  }
182  }
183 
188  template <Automaton Aut>
189  bool
190  is_letterized(const Aut& aut)
191  {
192  return detail::is_letterized(aut);
193  }
194 
195  namespace dyn
196  {
197  namespace detail
198  {
200  template <Automaton Aut>
201  bool is_letterized(const automaton& aut)
202  {
203  return ::vcsn::is_letterized(aut->as<Aut>());
204  }
205  }
206  }
207 
208  /*-----------.
209  | realtime. |
210  `-----------*/
211 
217  template <Automaton Aut>
218  auto
219  realtime(const Aut& aut)
220  -> decltype(proper(::vcsn::letterize(aut)))
221  {
222  return proper(::vcsn::letterize(aut));
223  }
224 
225  namespace dyn
226  {
227  namespace detail
228  {
230  template <Automaton Aut>
232  {
233  return ::vcsn::realtime(aut->as<Aut>());
234  }
235  }
236  }
237 
238  /*--------------.
239  | is_realtime. |
240  `--------------*/
241 
246  template <Automaton Aut>
247  bool
248  is_realtime(const Aut& aut)
249  {
251  }
252 
253  namespace dyn
254  {
255  namespace detail
256  {
258  template <Automaton Aut>
259  bool is_realtime(const automaton& aut)
260  {
261  return ::vcsn::is_realtime(aut->as<Aut>());
262  }
263  }
264  }
265 } // namespace vcsn
automaton realtime(const automaton &aut)
Bridge.
Definition: letterize.hh:231
context_t_of< out_automaton_t > out_ctx_t
Definition: letterize.hh:33
letterizer(const in_automaton_t &in_aut, const out_labelset_t &ls)
Definition: letterize.hh:42
auto proper(const Aut &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto") -> fresh_automaton_t_of< Aut, detail::proper_context< context_t_of< Aut >>>
Eliminate spontaneous transitions.
Definition: proper.hh:243
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
auto transitions(const Aut &aut) -> decltype(all_transitions(aut, is_special_t< Aut >
All the transition indexes between visible states.
Definition: automaton.hh:226
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
std::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, bool > is_letterized(const Aut &aut)
Definition: letterize.hh:161
From an automaton, the corresponding automaton with a non-word labelset.
Definition: letterize.hh:22
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:19
auto letterize(const Aut &aut) -> decltype(detail::letterize(aut))
Split the word transitions in the input automaton into letter ones.
Definition: letterize.hh:134
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
state_t_of< in_automaton_t > in_state_t
Definition: letterize.hh:27
std::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, mutable_automaton< letterized_context< context_t_of< Aut > > > > letterize(const Aut &aut)
Letterize an automaton whose type is not letterized already.
Definition: letterize.hh:106
letterized_t< LabelSet > make_letterized(const LabelSet &ls)
Definition: labelset.hh:99
state_t_of< out_automaton_t > out_state_t
Definition: letterize.hh:34
out_automaton_t letterize()
Definition: letterize.hh:48
constant< type_t::one, Context > one
Definition: fwd.hh:113
automaton letterize(const automaton &aut)
Bridge.
Definition: letterize.hh:146
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
bool is_realtime(const automaton &aut)
Bridge.
Definition: letterize.hh:259
Definition: a-star.hh:8
A dyn automaton.
Definition: automaton.hh:17
bool is_realtime(const Aut &aut)
Check if the automaton is realtime, i.e.
Definition: letterize.hh:248
bool is_letterized(const automaton &aut)
Bridge.
Definition: letterize.hh:201
typename in_labelset_t::value_t in_label_t
Definition: letterize.hh:29
std::vector< out_state_t > map_t
Definition: letterize.hh:40
A traits to compute the letterized context.
Definition: labelset.hh:78
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
typename out_labelset_t::value_t out_label_t
Definition: letterize.hh:36
context_t_of< in_automaton_t > in_ctx_t
Definition: letterize.hh:26
auto realtime(const Aut &aut) -> decltype(proper(::vcsn::letterize(aut)))
Split the word transitions in the input automaton into letter ones, and remove the spontaneous transi...
Definition: letterize.hh:219
labelset_t_of< out_automaton_t > out_labelset_t
Definition: letterize.hh:35
transition_t_of< in_automaton_t > in_transition_t
Definition: letterize.hh:30
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
transition_t_of< out_automaton_t > out_transition_t
Definition: letterize.hh:37
in_automaton_t in_aut_
Definition: letterize.hh:93
out_automaton_t out_aut_
Definition: letterize.hh:94
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
labelset_t_of< in_automaton_t > in_labelset_t
Definition: letterize.hh:28