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