Vcsn  2.2
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/fwd.hh>
9 #include <vcsn/core/rat/copy.hh>
10 #include <vcsn/dyn/automaton.hh>
11 #include <vcsn/dyn/context.hh>
12 #include <vcsn/dyn/expression.hh>
13 #include <vcsn/misc/attributes.hh>
14 #include <vcsn/misc/set.hh>
16 
17 namespace vcsn
18 {
19 
20  namespace detail
21  {
26  template <Automaton Aut>
28 
31  template <Automaton Aut>
32  auto
33  real_context(const Aut& aut)
34  -> decltype(real_context_impl<Aut>::context(aut));
35 
36  template <Automaton Aut>
37  struct real_context_impl
38  {
39  static auto context(const Aut& aut)
40  -> decltype(aut->context())
41  {
42  return aut->context();
43  }
44  };
45 
46  template <std::size_t Tape, Automaton Aut>
48  {
49  static auto context(const focus_automaton<Tape, Aut>& aut)
50  -> decltype(aut->full_context())
51  {
52  return aut->full_context();
53  }
54  };
55 
57  //
58  // FIXME: try to recurse on all automaton decorator types without
59  // listing them.
60  template <Automaton Aut>
62  {
63  static auto context(const automaton_decorator<Aut>& aut)
64  -> decltype(real_context(aut->strip()))
65  {
66  return real_context(aut->strip());
67  }
68  };
69 
70  template <Automaton Aut>
71  auto
72  real_context(const Aut& aut)
73  -> decltype(real_context_impl<Aut>::context(aut))
74  {
76  }
77  }
78 
87  template <Automaton AutIn,
88  Automaton AutOut = fresh_automaton_t_of<AutIn>>
89  AutOut
90  make_fresh_automaton(const AutIn& model)
91  {
92  // FIXME: here, we need a means to convert the given input context
93  // (e.g. letter -> B) into the destination one (e.g., letter ->
94  // Q). The automaton constructor wants the exact context type.
95  return make_shared_ptr<AutOut>(detail::real_context(model));
96  }
97 
98 
99  /*------------------.
100  | copy(automaton). |
101  `------------------*/
102 
103  namespace detail
104  {
112  template <Automaton AutIn, Automaton AutOut = AutIn>
113  class copier
114  {
115  public:
116  using in_automaton_t = AutIn;
117  using out_automaton_t = AutOut;
118 
122  using state_map_t = std::unordered_map<in_state_t, out_state_t>;
123 
124  private:
131  bool safe_ = true;
134 
135  public:
144  bool safe = true)
145  : in_(in)
146  , out_(out)
147  , safe_(safe)
148  , out_state_{{in_->pre(), out_->pre()},
149  {in_->post(), out_->post()}}
150  {}
151 
159  template <typename KeepState, typename KeepTrans>
160  void operator()(KeepState keep_state, KeepTrans keep_trans)
161  {
162  // Copy the states. We cannot iterate on the transitions
163  // only, as we would lose the states without transitions. And
164  // this way, we keep the states in the same order.
165  for (auto s: in_->states())
166  if (keep_state(s))
167  out_state_[s] = out_->new_state();
168 
169  for (auto t : all_transitions(in_))
170  if (keep_trans(t))
171  {
172  auto src = out_state_.find(in_->src_of(t));
173  auto dst = out_state_.find(in_->dst_of(t));
174  if (src != out_state_.end() && dst != out_state_.end())
175  {
176  if (safe_)
177  out_->new_transition_copy(src->second, dst->second,
178  in_, t);
179  else
180  out_->add_transition_copy(src->second, dst->second,
181  in_, t);
182  }
183  }
184  }
185 
189  template <typename Transitions>
190  auto operator()(const Transitions& ts)
191  -> decltype(ts[0] == in_->null_transition(), void())
192  {
193  for (auto t : ts)
194  operator()(t);
195  }
196 
201  {
202  auto src = state(in_->src_of(t));
203  auto dst = state(in_->dst_of(t));
204  if (safe_)
205  out_->new_transition_copy(src, dst, in_, t);
206  else
207  out_->add_transition_copy(src, dst, in_, t);
208  }
209 
211  void operator()()
212  {
213  operator()([](state_t_of<in_automaton_t>) { return true; },
214  [](transition_t_of<in_automaton_t>) { return true; });
215  }
216 
218  const state_map_t& state_map() const
219  {
220  return out_state_;
221  }
222 
225  {
226  return out_state_;
227  }
228 
229  private:
233  {
234  out_state_t res;
235  auto i = out_state_.find(s);
236  if (i == std::end(out_state_))
237  res = out_state_.emplace(s, out_->new_state()).first->second;
238  else
239  res = i->second;
240  return res;
241  }
242  };
243  }
244 
245 
247  template <Automaton AutIn, Automaton AutOut>
248  detail::copier<AutIn, AutOut>
249  make_copier(const AutIn& in, AutOut& out, bool safe = true)
250  {
251  return {in, out, safe};
252  }
253 
254 
257  template <Automaton AutIn, Automaton AutOut,
258  typename KeepState, typename KeepTrans>
259  void
260  copy_into(const AutIn& in, AutOut& out,
261  KeepState keep_state, KeepTrans keep_trans)
262  {
263  auto copy = make_copier(in, out);
264  copy(keep_state, keep_trans);
265  }
266 
269  template <Automaton AutIn, Automaton AutOut, typename KeepState>
270  void
271  copy_into(const AutIn& in, AutOut& out, KeepState keep_state)
272  {
273  return copy_into(in, out, keep_state,
274  [](transition_t_of<AutIn>) { return true; });
275  }
276 
277 
280  template <Automaton AutIn, Automaton AutOut>
281  void
282  copy_into(const AutIn& in, AutOut& out)
283  {
284  return copy_into(in, out,
285  [](state_t_of<AutIn>) { return true; },
286  [](transition_t_of<AutIn>) { return true; });
287  }
288 
289 
292  template <Automaton AutIn, Automaton AutOut>
293  void
294  copy_into(const AutIn& in, AutOut& out, bool safe)
295  {
296  auto copy = make_copier(in, out, safe);
297  copy([](state_t_of<AutIn>) { return true; },
298  [](transition_t_of<AutIn>) { return true; });
299  }
300 
301 
304  template <Automaton AutIn,
305  Automaton AutOut = fresh_automaton_t_of<AutIn>,
306  typename KeepState, typename KeepTrans>
307  auto
308  copy(const AutIn& input, KeepState keep_state, KeepTrans keep_trans)
309  -> decltype(keep_state(input->null_state()),
310  keep_trans(input->null_transition()),
311  make_fresh_automaton<AutIn, AutOut>(input))
312  {
313  auto res = make_fresh_automaton<AutIn, AutOut>(input);
314  ::vcsn::copy_into(input, res, keep_state, keep_trans);
315  return res;
316  }
317 
318 
320  template <Automaton AutIn,
321  Automaton AutOut = fresh_automaton_t_of<AutIn>,
322  typename KeepState>
323  auto
324  copy(const AutIn& input, KeepState keep_state)
325  -> decltype(keep_state(input->null_state()),
326  make_fresh_automaton<AutIn, AutOut>(input))
327  {
328  return ::vcsn::copy<AutIn, AutOut>(
329  input,
330  keep_state,
331  [](transition_t_of<AutIn>) { return true; }
332  );
333  }
334 
335 
337  template <Automaton AutIn,
338  Automaton AutOut = fresh_automaton_t_of<AutIn>>
339  AutOut
340  copy(const AutIn& input)
341  {
342  return ::vcsn::copy<AutIn, AutOut>(
343  input,
344  [](state_t_of<AutIn>) { return true; },
345  [](transition_t_of<AutIn>) { return true; }
346  );
347  }
348 
349 
352  template <Automaton AutIn,
353  Automaton AutOut = fresh_automaton_t_of<AutIn>,
354  typename States>
355  auto
356  copy(const AutIn& input, const States& ss)
357  -> decltype(*ss.begin() == input->null_state(),
358  make_fresh_automaton<AutIn, AutOut>(input))
359  {
360  return ::vcsn::copy<AutIn, AutOut>
361  (input,
362  [&ss](state_t_of<AutIn> s) { return has(ss, s); });
363  }
364 
365 
369  template <Automaton AutIn,
370  Automaton AutOut = fresh_automaton_t_of<AutIn>,
371  typename States, typename Trans>
372  auto
373  copy(const AutIn& input, const States& ss, const Trans& ts)
374  -> decltype(*ss.begin() == input->null_state(),
375  *ts.begin() == input->null_transition(),
376  make_fresh_automaton<AutIn, AutOut>(input))
377  {
378  return ::vcsn::copy<AutIn, AutOut>
379  (input,
380  [&ss](state_t_of<AutIn> s) { return has(ss, s); },
381  [&ts](transition_t_of<AutIn> t) { return has(ts, t); });
382  }
383 
384 
387  template <Automaton AutIn,
388  Automaton AutOut = fresh_automaton_t_of<AutIn>,
389  typename Transitions>
390  auto
391  copy(const AutIn& input, const Transitions& ts)
392  -> decltype(*ts.begin() == input->null_transition(),
393  make_fresh_automaton<AutIn, AutOut>(input))
394  {
395  auto res = make_fresh_automaton<AutIn, AutOut>(input);
396  auto copy = make_copier(input, res);
397  copy(ts);
398  return res;
399  }
400 
401 
402  namespace dyn
403  {
404  namespace detail
405  {
407  template <Automaton Aut, typename Ctx>
408  automaton
409  copy_convert(const automaton& aut, const context& ctx)
410  {
411  const auto& a = aut->as<Aut>();
412  const auto& c = ctx->as<Ctx>();
413  auto res = make_mutable_automaton(c);
414  ::vcsn::copy_into(a, res);
415  return make_automaton(res);
416  }
417 
419  template <Automaton Aut>
420  automaton
421  copy(const automaton& aut)
422  {
423  const auto& a = aut->as<Aut>();
424  return make_automaton(::vcsn::copy(a));
425  }
426  }
427  }
428 
429  /*--------------------.
430  | copy(expression). |
431  `--------------------*/
432 
433  namespace dyn
434  {
435  namespace detail
436  {
438  template <typename ExpSet, typename Context, typename Identities>
439  expression
441  const context& ctx, rat::identities ids)
442  {
443  const auto& r = exp->as<ExpSet>();
444  const auto& c = ctx->as<Context>();
445  const auto& rs = make_expressionset(c, ids);
446 
447  return make_expression(rs,
448  ::vcsn::rat::copy(r.expressionset(), rs,
449  r.expression()));
450  }
451  }
452  }
453 
454 
455 
456 } // namespace vcsn
std::shared_ptr< detail::focus_automaton_impl< Tape, Aut >> focus_automaton
A focus automaton as a shared pointer.
Definition: fwd.hh:42
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:72
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
copier(const in_automaton_t &in, out_automaton_t &out, bool safe=true)
Prepare for an automaton full/partial duplication.
Definition: copy.hh:143
void operator()()
Copy all the states, and all the transitions.
Definition: copy.hh:211
AutOut out_automaton_t
Definition: copy.hh:117
void operator()(KeepState keep_state, KeepTrans keep_trans)
Copy some states, and some transitions.
Definition: copy.hh:160
An expressionset can implement several different sets of identities on expressions.
Definition: identities.hh:21
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:260
AutIn in_automaton_t
Definition: copy.hh:116
Definition: a-star.hh:8
state_t_of< out_automaton_t > out_state_t
Definition: copy.hh:120
static auto context(const focus_automaton< Tape, Aut > &aut) -> decltype(aut->full_context())
Definition: copy.hh:49
state_map_t & state_map()
A map from original state to result state.
Definition: copy.hh:224
out_state_t state(const in_state_t &s)
The out state corresponding to the in-state s.
Definition: copy.hh:232
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
in_automaton_t in_
Input automaton.
Definition: copy.hh:126
auto operator()(const Transitions &ts) -> decltype(ts[0]==in_->null_transition(), void())
Copy some transitions, and their corresponding states.
Definition: copy.hh:190
out_automaton_t out_
Output automaton.
Definition: copy.hh:128
static auto context(const Aut &aut) -> decltype(aut->context())
Definition: copy.hh:39
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
void copy_into(const AutIn &in, AutOut &out, bool safe)
Copy an automaton.
Definition: copy.hh:294
expression copy_expression(const expression &exp, const context &ctx, rat::identities ids)
Bridge (copy).
Definition: copy.hh:440
std::shared_ptr< const detail::context_base > context
A dyn::context.
Definition: fwd.hh:43
void operator()(const transition_t_of< in_automaton_t > &t)
Copy one transition, and its corresponding states.
Definition: copy.hh:200
Aggregate an automaton, and forward calls to it.
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
auto rs
Definition: lift.hh:151
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
bool safe_
whether the input automaton is in normal form and never has two transitions with same (src...
Definition: copy.hh:131
std::unordered_map< in_state_t, out_state_t > state_map_t
input state -> output state.
Definition: copy.hh:122
expressionset< Context > make_expressionset(const Context &ctx, rat::identities identities={})
Shorthand to expressionset constructor.
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
const state_map_t & state_map() const
A map from original state to result state.
Definition: copy.hh:218
state_map_t out_state_
input state -> output state.
Definition: copy.hh:133
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
automaton copy(const automaton &aut)
Bridge.
Definition: copy.hh:421
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:90
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
Copy an automaton.
Definition: copy.hh:113
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:183
static auto context(const automaton_decorator< Aut > &aut) -> decltype(real_context(aut->strip()))
Definition: copy.hh:63
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:249
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
auto all_transitions(const Aut &aut)
All the transition indexes between all states (including pre and post).
Definition: automaton.hh:184
#define Automaton
Definition: automaton.hh:24
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:105
expression make_expression(const ExpSet &rs, const typename ExpSet::value_t &r)
Definition: expression.hh:97
When we copy a focus automaton, create another focus automaton.
Definition: copy.hh:27
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:308
automaton copy_convert(const automaton &aut, const context &ctx)
Bridge (copy).
Definition: copy.hh:409
state_t_of< in_automaton_t > in_state_t
Definition: copy.hh:119