Awali
Another Weighted Automata library
outsplit.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_OUTSPLIT_HH
18 # define AWALI_ALGOS_OUTSPLIT_HH
19 
20 # include <unordered_set>
21 
23 #include <awali/sttc/algos/copy.hh>
24 #include <awali/sttc/misc/pair.hh>
26 #include <awali/sttc/algos/sort.hh>
27 
28 namespace awali { namespace sttc {
29 
30  namespace internal
31  {
32  //In place outsplitter
33  template <typename Aut>
35  {
36  using automaton_t = Aut;
37  using label_t = label_t_of<automaton_t>;
38 
39  public:
40  //Pred : Aut, transition_t -> bool
41  template <typename Pred>
42  void operator()(Aut& aut, const Pred& pred)
43  {
44  std::unordered_set<state_t> add_states;
45  for (auto st : aut->states())
46  {
47  if(add_states.find(st)!=add_states.end())
48  continue;
49  bool true_out = false;
50 
51  std::vector<transition_t> false_transitions;
52  for (auto tr : aut->all_out(st))
53  {
54  if(pred(aut,tr))
55  true_out = true;
56  else
57  false_transitions.emplace_back(tr);
58  }
59  if(true_out && !false_transitions.empty()) {
60  state_t ns=aut->add_state();
61  aut->set_state_name(ns, aut->get_state_name(st)+"'");
62  add_states.emplace(ns);
63  for(auto tr : false_transitions) {
64  aut->set_transition(ns, aut->dst_of(tr),
65  aut->label_of(tr), aut->weight_of(tr));
66  aut->del_transition(tr);
67  }
68  for(auto tr : aut->all_in(st)) {
69  aut->set_transition(aut->src_of(tr),ns,
70  aut->label_of(tr), aut->weight_of(tr));
71  }
72  }
73  }
74  }
75 
76  };
77 
78  template <typename Labelset,size_t I> struct select_one;
79  template <typename... T,size_t I>
80  struct select_one<tupleset<T...>,I>{
81  using tp_t = tupleset<T...>;
82 
83  static constexpr
84  bool has_one() {
85  return std::tuple_element<I,std::tuple<T...>>::type::has_one();
86  }
87 
88  template<typename LS, typename Tuple>
89  static
90  bool get(LS ts, Tuple tu) {
91  return std::get<I>(ts->sets()).is_one(std::get<I>(tu));
92  }
93  };
94  } // namespace internal
95 
96 
97  template<size_t I, typename Aut>
98  typename std::enable_if<internal::select_one<labelset_t_of<Aut>,I>::has_one(), void>::type
99  outsplit_here(Aut& aut)
100  {
102  auto ls=aut->context().labelset();
103  split(aut, [ls](const Aut& aut_, transition_t tr) {
104  return internal::select_one<labelset_t_of<Aut>,I>::get(ls,aut_->label_of(tr));
105  });
106  }
107 
108  template<size_t I, typename Aut>
109  typename std::enable_if<!internal::select_one<labelset_t_of<Aut>,I>::has_one(), void>::type
111  {}
112 
113  template <size_t I, typename Aut>
114  inline
115  Aut
116  outsplit(const Aut& aut, bool keep_history=true)
117  {
118  auto a = copy(aut, keep_history);
119  outsplit_here<I>(a);
120  sort_tape<I>(a);
121  return a;
122  }
123 
124 }}//end of ns awali::stc
125 
126 #endif // !AWALI_ALGOS_OUTSPLIT_HH
Definition: outsplit.hh:35
void operator()(Aut &aut, const Pred &pred)
Definition: outsplit.hh:42
A ValueSet which is a Cartesian product of ValueSets.
Definition: tupleset.hh:80
Definition: outsplit.hh:78
typename internal::label_t_of_impl< internal::base_t< ValueSet > >::type label_t_of
Helper to retrieve the type of the labels of a value set.
Definition: traits.hh:71
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
std::enable_if< internal::select_one< labelset_t_of< Aut >, I >::has_one(), void >::type outsplit_here(Aut &aut)
Definition: outsplit.hh:99
rat::ratexp_polynomial_t< RatExpSet > split(const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
Split a ratexp.
Definition: split.hh:243
Aut outsplit(const Aut &aut, bool keep_history=true)
Definition: outsplit.hh:116
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
unsigned transition_t
Definition: types.hh:22
static bool get(LS ts, Tuple tu)
Definition: outsplit.hh:90
static constexpr bool has_one()
Definition: outsplit.hh:84