Awali
Another Weighted Automata library
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
copy.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_COPY_HH
18 # define AWALI_ALGOS_COPY_HH
19 
20 # include <unordered_map>
21 
25 #include <awali/sttc/misc/set.hh>
27 
28 namespace awali { namespace sttc {
29 
30 
31  /*------------------.
32  | copy(automaton). |
33  `------------------*/
34 
35  namespace internal
36  {
39  template <typename AutIn, typename AutOut, typename InOutMap=std::unordered_map<state_t, state_t>>
40  struct copier
41  {
42  copier(const AutIn& in, AutOut& out)
43  : in_(in)
44  , out_(out)
45  {}
46 
47  template <typename Pred>
48  void operator()(Pred keep_state, bool transpose=false)
49  {
50  // Copy the states. We cannot iterate on the transitions
51  // only, as we would lose the states without transitions.
52  out_state[in_->pre()] = out_->pre();
53  out_state[in_->post()] = out_->post();
54  for (auto s: in_->states())
55  if (keep_state(s))
56  out_state[s] = out_->add_state();
57 
58  for (auto t : in_->all_transitions())
59  {
60  auto src = out_state.find(in_->src_of(t));
61  auto dst = out_state.find(in_->dst_of(t));
62  if (src != out_state.end() && dst != out_state.end())
63  out_->new_transition_copy(src->second, dst->second,
64  in_, t, transpose);
65  }
66  }
67 
68  template <typename Pred>
69  void no_weight(Pred keep_state)
70  {
71  // Copy the states. We cannot iterate on the transitions
72  // only, as we would lose the states without transitions.
73  out_state[in_->pre()] = out_->pre();
74  out_state[in_->post()] = out_->post();
75  for (auto s: in_->states())
76  if (keep_state(s))
77  out_state[s] = out_->add_state();
78 
79  for (auto t : in_->all_transitions())
80  {
81  auto src = out_state.find(in_->src_of(t));
82  auto dst = out_state.find(in_->dst_of(t));
83  if (src != out_state.end() && dst != out_state.end())
84  out_->new_transition(src->second, dst->second,
85  in_->label_of(t));
86  }
87  }
88 
90  using origins_t = std::map<state_t, state_t>;
91  origins_t
92  origins() const
93  {
94  origins_t res;
95  for (const auto& p: out_state)
96  res[p.second] = p.first;
97  return res;
98  }
99 
101  static
102  std::ostream&
103  print(const origins_t& orig, std::ostream& o)
104  {
105  o << "/* Origins.\n"
106  << " node [shape = box, style = rounded]\n";
107  for (auto p : orig)
108  if (2 <= p.first)
109  o << " " << p.first - 2
110  << " [label = \"" << p.second - 2 << "\"]\n";
111  o << "*/\n";
112  return o;
113  }
114 
115  void set_history() {
116  auto history = std::make_shared<single_history<AutIn>>(in_);
117  out_->set_history(history);
118  for (auto p: in_->all_states()) {
119  history->add_state(out_state[p], p);
120  if(in_->has_name(p)) {
121  out_->set_state_name(out_state[p], in_->get_state_name(p));
122  }
123  }
124  }
125 
126  const InOutMap& in_out_map() const {
127  return out_state;
128  }
129 
131  const AutIn& in_;
133  AutOut& out_;
135  InOutMap out_state;
136  };
137  }
138 
141  template <typename AutIn, typename AutOut, typename Pred>
142  inline
143  void
144  copy_into(const AutIn& in, AutOut& out, Pred keep_state, bool keep_history=true, bool transpose=false)
145  {
147  copy(keep_state, transpose);
148  if(keep_history)
149  copy.set_history();
150  }
151 
152  template <typename AutIn, typename AutOut>
153  inline
154  void
155  copy_into(const AutIn& in, AutOut& out, bool keep_history=true, bool transpose=false)
156  {
157  copy_into(in, out, [](state_t) { return true; }, keep_history, transpose);
158  }
159 
160  template <typename AutIn, typename AutOut, typename Pred>
161  inline
162  void
163  copy_support(const AutIn& in, AutOut& out, Pred keep_state, bool keep_history=true)
164  {
166  copy.no_weight(keep_state);
167  if(keep_history)
168  copy.set_history();
169  }
170 
171  template <typename AutIn, typename AutOut>
172  inline
173  void
174  copy_support(const AutIn& in, AutOut& out, bool keep_history=true)
175  {
177  copy.no_weight([](state_t) { return true; });
178  if(keep_history)
179  copy.set_history();
180  }
181 
184  template <typename AutIn,
185  typename AutOut = typename AutIn::element_type::automaton_nocv_t,
186  typename Pred>
187  inline
188  AutOut
189  copy(const AutIn& input, Pred keep_state, bool keep_history=true, bool transpose=false)
190  {
191  // FIXME: here, we need a means to convert the given input context
192  // (e.g. letter -> B) into the destination one (e.g., letter ->
193  // Q). The automaton constructor wants the exact context type.
194  auto res = make_mutable_automaton(input->context());
195  sttc::copy_into(input, res, keep_state, keep_history, transpose);
196  res->set_name(input->get_name());
197  res->set_desc(input->get_desc());
198  return res;
199  }
200 
202  template <typename AutIn,
203  typename AutOut = typename AutIn::element_type::automaton_nocv_t>
204  inline
205  AutOut
206  copy(const AutIn& input, bool keep_history=true, bool transpose=false)
207  {
208  return sttc::copy<AutIn, AutOut>(input,
209  [](state_t) { return true; }, keep_history, transpose);
210  }
211 
214  template <typename AutIn,
215  typename AutOut = typename AutIn::element_type::automaton_nocv_t>
216  inline
217  AutOut
218  copy(const AutIn& input, const std::set<state_t>& keep, bool keep_history=true, bool transpose=false)
219  {
220  return sttc::copy<AutIn, AutOut>
221  (input,
222  [&keep](state_t s) { return keep.find(s)!=keep.end(); }, keep_history, transpose);
223  }
224 
225 }}//end of ns awali::stc
226 
227 #endif // !AWALI_ALGOS_COPY_HH
void copy_support(const AutIn &in, AutOut &out, Pred keep_state, bool keep_history=true)
Definition: copy.hh:163
void copy_into(const AutIn &in, AutOut &out, Pred keep_state, bool keep_history=true, bool transpose=false)
Copy an automaton.
Definition: copy.hh:144
AutOut transpose(Aut &aut, bool keep_history=true)
Definition: transpose.hh:79
AutOut copy(const AutIn &input, Pred keep_state, bool keep_history=true, bool transpose=false)
A copy of input keeping only its states that are accepted by keep_state.
Definition: copy.hh:189
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
Definition: mutable_automaton.hh:915
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
Copy an automaton.
Definition: copy.hh:41
const AutIn & in_
Input automaton.
Definition: copy.hh:131
static std::ostream & print(const origins_t &orig, std::ostream &o)
Print the origins.
Definition: copy.hh:103
origins_t origins() const
Definition: copy.hh:92
const InOutMap & in_out_map() const
Definition: copy.hh:126
InOutMap out_state
input state -> output state.
Definition: copy.hh:135
void no_weight(Pred keep_state)
Definition: copy.hh:69
copier(const AutIn &in, AutOut &out)
Definition: copy.hh:42
void operator()(Pred keep_state, bool transpose=false)
Definition: copy.hh:48
std::map< state_t, state_t > origins_t
A map from result state to original state.
Definition: copy.hh:90
AutOut & out_
Output automaton.
Definition: copy.hh:133
void set_history()
Definition: copy.hh:115