Vcsn  2.3a
Be Rational
copy.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <unordered_map>
4 
5 #include <vcsn/algos/fwd.hh> // focus_automaton.
7 #include <vcsn/core/automaton.hh>
8 #include <vcsn/core/fwd.hh>
10 #include <vcsn/core/rat/copy.hh>
11 #include <vcsn/dyn/automaton.hh>
12 #include <vcsn/dyn/context.hh>
13 #include <vcsn/dyn/types.hh>
14 #include <vcsn/dyn/value.hh>
15 #include <vcsn/misc/attributes.hh>
16 #include <vcsn/misc/set.hh>
18 
19 namespace vcsn
20 {
21 
22  namespace detail
23  {
27  template <Automaton Aut>
29 
32  template <Automaton Aut>
33  auto
34  real_context(const Aut& aut)
35  -> decltype(real_context_impl<Aut>::context(aut));
36 
37  template <Automaton Aut>
38  struct real_context_impl
39  {
40  static auto context(const Aut& aut)
41  -> decltype(aut->context())
42  {
43  return aut->context();
44  }
45  };
46 
47  template <std::size_t Tape, Automaton Aut>
49  {
50  static auto context(const focus_automaton<Tape, Aut>& aut)
51  -> decltype(aut->full_context())
52  {
53  return aut->full_context();
54  }
55  };
56 
58  //
59  // FIXME: try to recurse on all automaton decorator types without
60  // listing them.
61  template <Automaton Aut>
63  {
64  static auto context(const automaton_decorator<Aut>& aut)
65  -> decltype(real_context(aut->strip()))
66  {
67  return real_context(aut->strip());
68  }
69  };
70 
71  template <Automaton Aut>
72  auto
73  real_context(const Aut& aut)
74  -> decltype(real_context_impl<Aut>::context(aut))
75  {
77  }
78  }
79 
88  template <Automaton AutIn,
89  Automaton AutOut = fresh_automaton_t_of<AutIn>>
90  AutOut
91  make_fresh_automaton(const AutIn& model)
92  {
93  // FIXME: here, we need a means to convert the given input context
94  // (e.g. letter -> B) into the destination one (e.g., letter ->
95  // Q). The automaton constructor wants the exact context type.
96  return make_shared_ptr<AutOut>(detail::real_context(model));
97  }
98 
99 
100  /*------------------.
101  | copy(automaton). |
102  `------------------*/
103 
104  namespace detail
105  {
113  template <Automaton AutIn, Automaton AutOut = AutIn>
114  class copier
115  {
116  public:
117  using in_automaton_t = AutIn;
118  using out_automaton_t = AutOut;
119 
123  using state_map_t = std::unordered_map<in_state_t, out_state_t>;
124 
125  private:
132  bool safe_ = true;
135 
136  public:
145  bool safe = true)
146  : in_(in)
147  , out_(out)
148  , safe_(safe)
149  , out_state_{{in_->pre(), out_->pre()},
150  {in_->post(), out_->post()}}
151  {}
152 
160  template <typename KeepState, typename KeepTrans>
161  void operator()(KeepState keep_state, KeepTrans keep_trans)
162  {
163  // Copy the states. We cannot iterate on the transitions
164  // only, as we would lose the states without transitions. And
165  // this way, we keep the states in the same order.
166  for (auto s: in_->states())
167  if (keep_state(s))
168  out_state_[s] = out_->new_state();
169 
170  for (auto t : all_transitions(in_))
171  if (keep_trans(t))
172  {
173  auto src = out_state_.find(in_->src_of(t));
174  auto dst = out_state_.find(in_->dst_of(t));
175  if (src != out_state_.end() && dst != out_state_.end())
176  {
177  if (safe_)
178  out_->new_transition_copy(src->second, dst->second,
179  in_, t);
180  else
181  out_->add_transition_copy(src->second, dst->second,
182  in_, t);
183  }
184  }
185  }
186 
190  template <typename Transitions>
191  auto operator()(const Transitions& ts)
192  -> decltype(ts[0] == in_->null_transition(), void())
193  {
194  for (auto t : ts)
195  operator()(t);
196  }
197 
202  {
203  auto src = state(in_->src_of(t));
204  auto dst = state(in_->dst_of(t));
205  if (safe_)
206  out_->new_transition_copy(src, dst, in_, t);
207  else
208  out_->add_transition_copy(src, dst, in_, t);
209  }
210 
212  void operator()()
213  {
214  operator()([](state_t_of<in_automaton_t>) { return true; },
215  [](transition_t_of<in_automaton_t>) { return true; });
216  }
217 
219  const state_map_t& state_map() const
220  {
221  return out_state_;
222  }
223 
226  {
227  return out_state_;
228  }
229 
230  private:
234  {
236  auto i = out_state_.find(s);
237  if (i == std::end(out_state_))
238  res = out_state_.emplace(s, out_->new_state()).first->second;
239  else
240  res = i->second;
241  return res;
242  }
243  };
244  }
245 
246 
254  template <Automaton AutIn, Automaton AutOut>
255  detail::copier<AutIn, AutOut>
256  make_copier(const AutIn& in, AutOut& out, bool safe = true)
257  {
258  return {in, out, safe};
259  }
260 
261 
264  template <Automaton AutIn, Automaton AutOut,
265  typename KeepState, typename KeepTrans>
266  void
267  copy_into(const AutIn& in, AutOut& out,
268  KeepState keep_state, KeepTrans keep_trans)
269  {
270  auto copy = make_copier(in, out);
271  copy(keep_state, keep_trans);
272  }
273 
276  template <Automaton AutIn, Automaton AutOut, typename KeepState>
277  void
278  copy_into(const AutIn& in, AutOut& out, KeepState keep_state)
279  {
280  return copy_into(in, out, keep_state,
281  [](transition_t_of<AutIn>) { return true; });
282  }
283 
284 
287  template <Automaton AutIn, Automaton AutOut>
288  void
289  copy_into(const AutIn& in, AutOut& out)
290  {
291  return copy_into(in, out,
292  [](state_t_of<AutIn>) { return true; },
293  [](transition_t_of<AutIn>) { return true; });
294  }
295 
296 
306  template <Automaton AutIn, Automaton AutOut>
307  void
308  copy_into(const AutIn& in, AutOut& out, bool safe)
309  {
310  auto copy = make_copier(in, out, safe);
311  copy([](state_t_of<AutIn>) { return true; },
312  [](transition_t_of<AutIn>) { return true; });
313  }
314 
315 
318  template <Automaton AutIn,
319  Automaton AutOut = fresh_automaton_t_of<AutIn>,
320  typename KeepState, typename KeepTrans>
321  auto
322  copy(const AutIn& input, KeepState keep_state, KeepTrans keep_trans)
323  -> decltype(keep_state(input->null_state()),
324  keep_trans(input->null_transition()),
325  make_fresh_automaton<AutIn, AutOut>(input))
326  {
327  auto res = make_fresh_automaton<AutIn, AutOut>(input);
328  ::vcsn::copy_into(input, res, keep_state, keep_trans);
329  return res;
330  }
331 
332 
334  template <Automaton AutIn,
335  Automaton AutOut = fresh_automaton_t_of<AutIn>,
336  typename KeepState>
337  auto
338  copy(const AutIn& input, KeepState keep_state)
339  -> decltype(keep_state(input->null_state()),
340  make_fresh_automaton<AutIn, AutOut>(input))
341  {
342  return ::vcsn::copy<AutIn, AutOut>(
343  input,
344  keep_state,
345  [](transition_t_of<AutIn>) { return true; }
346  );
347  }
348 
349 
351  template <Automaton AutIn,
352  Automaton AutOut = fresh_automaton_t_of<AutIn>>
353  AutOut
354  copy(const AutIn& input)
355  {
356  return ::vcsn::copy<AutIn, AutOut>(
357  input,
358  [](state_t_of<AutIn>) { return true; },
359  [](transition_t_of<AutIn>) { return true; }
360  );
361  }
362 
363 
366  template <Automaton AutIn,
367  Automaton AutOut = fresh_automaton_t_of<AutIn>,
368  typename States>
369  auto
370  copy(const AutIn& input, const States& ss)
371  -> decltype(*ss.begin() == input->null_state(),
372  make_fresh_automaton<AutIn, AutOut>(input))
373  {
374  return ::vcsn::copy<AutIn, AutOut>
375  (input,
376  [&ss](state_t_of<AutIn> s) { return has(ss, s); });
377  }
378 
379 
383  template <Automaton AutIn,
384  Automaton AutOut = fresh_automaton_t_of<AutIn>,
385  typename States, typename Trans>
386  auto
387  copy(const AutIn& input, const States& ss, const Trans& ts)
388  -> decltype(*ss.begin() == input->null_state(),
389  *ts.begin() == input->null_transition(),
390  make_fresh_automaton<AutIn, AutOut>(input))
391  {
392  return ::vcsn::copy<AutIn, AutOut>
393  (input,
394  [&ss](state_t_of<AutIn> s) { return has(ss, s); },
395  [&ts](transition_t_of<AutIn> t) { return has(ts, t); });
396  }
397 
398 
401  template <Automaton AutIn,
402  Automaton AutOut = fresh_automaton_t_of<AutIn>,
403  typename Transitions>
404  auto
405  copy(const AutIn& input, const Transitions& ts)
406  -> decltype(*ts.begin() == input->null_transition(),
407  make_fresh_automaton<AutIn, AutOut>(input))
408  {
409  auto res = make_fresh_automaton<AutIn, AutOut>(input);
410  auto copy = make_copier(input, res);
411  copy(ts);
412  return res;
413  }
414 
415 
416  namespace dyn
417  {
418  namespace detail
419  {
421  template <Automaton Aut, typename Ctx>
422  automaton
423  copy_convert(const automaton& aut, const context& ctx)
424  {
425  const auto& a = aut->as<Aut>();
426  const auto& c = ctx->as<Ctx>();
427  auto res = make_mutable_automaton(c);
428  ::vcsn::copy_into(a, res);
429  return res;
430  }
431 
433  template <Automaton Aut>
434  automaton
435  copy(const automaton& aut)
436  {
437  const auto& a = aut->as<Aut>();
439  }
440  }
441  }
442 
443  /*--------------------.
444  | copy(expression). |
445  `--------------------*/
446 
447  namespace dyn
448  {
449  namespace detail
450  {
452  template <typename ExpSet, typename Context, typename Identities>
453  expression
455  const context& ctx, identities ids)
456  {
457  const auto& r = exp->as<ExpSet>();
458  const auto& c = ctx->as<Context>();
459  const auto& rs = make_expressionset(c, ids);
460 
461  return {rs, ::vcsn::rat::copy(r.valueset(),
462  rs,
463  r.value())};
464  }
465  }
466  }
467 } // namespace vcsn
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
void operator()()
Copy all the states, and all the transitions.
Definition: copy.hh:212
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
std::shared_ptr< detail::focus_automaton_impl< Tape, Aut >> focus_automaton
A focus automaton as a shared pointer.
Definition: fwd.hh:42
bool safe_
whether the input automaton is in normal form and never has two transitions with same (src...
Definition: copy.hh:132
void operator()(KeepState keep_state, KeepTrans keep_trans)
Copy some states, and some transitions.
Definition: copy.hh:161
std::unordered_map< in_state_t, out_state_t > state_map_t
input state -> output state.
Definition: copy.hh:123
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:84
AutIn in_automaton_t
Definition: copy.hh:117
Definition: a-star.hh:8
return res
Definition: multiply.hh:398
state_map_t & state_map()
A map from original state to result state.
Definition: copy.hh:225
automaton copy(const automaton &aut)
Bridge.
Definition: copy.hh:435
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Aggregate an automaton, and forward calls to it.
AutOut out_automaton_t
Definition: copy.hh:118
state_map_t out_state_
input state -> output state.
Definition: copy.hh:134
auto operator()(const Transitions &ts) -> decltype(ts[0]==in_->null_transition(), void())
Copy some transitions, and their corresponding states.
Definition: copy.hh:191
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
state_t_of< out_automaton_t > out_state_t
Definition: copy.hh:121
auto & as()
Downcast to the exact type.
Definition: context.hh:36
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
static auto context(const focus_automaton< Tape, Aut > &aut) -> decltype(aut->full_context())
Definition: copy.hh:50
in_automaton_t in_
Input automaton.
Definition: copy.hh:127
static auto context(const Aut &aut) -> decltype(aut->context())
Definition: copy.hh:40
expression copy_expression(const expression &exp, const context &ctx, identities ids)
Bridge (copy).
Definition: copy.hh:454
OutExpSet::value_t copy(const InExpSet &in_rs, const OutExpSet &out_rs, const typename InExpSet::value_t &v)
Copy/convert a rational expression.
Definition: copy.hh:174
Template-less root for contexts.
Definition: context.hh:16
void copy_into(const AutIn &in, AutOut &out, bool safe)
Copy an automaton.
Definition: copy.hh:308
When we copy a focus automaton, we create another focus automaton.
Definition: copy.hh:28
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:212
copier(const in_automaton_t &in, out_automaton_t &out, bool safe=true)
Prepare for an automaton full/partial duplication.
Definition: copy.hh:144
A dyn automaton.
Definition: automaton.hh:17
Copy an automaton.
Definition: copy.hh:114
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
automaton copy_convert(const automaton &aut, const context &ctx)
Bridge (copy).
Definition: copy.hh:423
auto rs
Definition: lift.hh:152
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
out_state_t state(const in_state_t &s)
The out state corresponding to the in-state s.
Definition: copy.hh:233
const state_map_t & state_map() const
A map from original state to result state.
Definition: copy.hh:219
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:133
#define Automaton
Definition: automaton.hh:23
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
auto real_context(const Aut &aut) -> decltype(real_context_impl< Aut >::context(aut))
For a focus automaton, its genuine context (not the visible one), and for all the other automata...
Definition: copy.hh:73
auto make_expressionset(const context< LabelSet, WeightSet > &ctx, rat::identities ids={}) -> expressionset< context< LabelSet, WeightSet >>
Shorthand to expressionset constructor.
state_t_of< in_automaton_t > in_state_t
Definition: copy.hh:120
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
out_automaton_t out_
Output automaton.
Definition: copy.hh:129
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
void operator()(const transition_t_of< in_automaton_t > &t)
Copy one transition, and its corresponding states.
Definition: copy.hh:201
static auto context(const automaton_decorator< Aut > &aut) -> decltype(real_context(aut->strip()))
Definition: copy.hh:64
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46