Awali
Another Weighted Automata library
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
transition_map.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_CORE_TRANSITION_MAP_HH
18 # define AWALI_CORE_TRANSITION_MAP_HH
19 
20 # include <map>
21 # include <type_traits>
22 
23 namespace awali { namespace sttc {
24 
25  namespace internal
26  {
27 
41  template <typename Aut,
42  typename WeightSet = weightset_t_of<Aut>,
43  bool Deterministic = false,
44  bool AllOut = false>
46  {
47  using weightset_t = WeightSet;
48  using weight_t = typename weightset_t::value_t;
49  struct transition
50  {
54  };
55 
57  = typename std::conditional<Deterministic,
58  transition,
59  std::vector<transition>>::type;
60  using map_t = std::map<label_t_of<Aut>, transitions_t>;
61  using maps_t = std::map<state_t, map_t>;
63 
64  transition_map(const Aut& aut, const weightset_t& ws)
65  : aut_(aut)
66  , ws_(ws)
67  {}
68 
69  transition_map(const Aut& aut)
70  : transition_map(aut, *aut->weightset())
71  {}
72 
74  template <bool Deterministic_>
75  void
78  typename std::enable_if<Deterministic_>::type* = nullptr)
79  {
80  map.emplace(l, t);
81  }
82 
84  template <bool Deterministic_>
85  void
88  typename std::enable_if<!Deterministic_>::type* = nullptr)
89  {
90  map[l].emplace_back(t);
91  }
92 
95  map_t&
96  build_map_(typename maps_t::iterator lb, state_t s)
97  {
98  auto& res = maps_.emplace_hint(lb, s, map_t{})->second;
99  for (auto t: aut_->all_out(s))
100  if (AllOut || !aut_->labelset()->is_special(aut_->label_of(t)))
101  {
102  auto w = ws_.conv(*aut_->weightset(), aut_->weight_of(t));
103  insert_<Deterministic>(res,
104  aut_->label_of(t),
105  transition{w, aut_->dst_of(t)});
106  }
107  return res;
108  }
109 
111  {
112  auto lb = maps_.lower_bound(s);
113  if (lb == maps_.end() || maps_.key_comp()(s, lb->first))
114  return build_map_(lb, s);
115  else
116  return lb->second;
117  }
118 
120  const Aut& aut_;
122  const weightset_t& ws_;
123  };
124  }
125 
126 }}//end of ns awali::stc
127 
128 #endif // !AWALI_CORE_TRANSITION_MAP_HH
weightset_description weightset(const std::string &k)
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:134
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
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
Cache the outgoing transitions of an automaton as efficient maps label -> vector<(weight,...
Definition: transition_map.hh:46
typename std::conditional< Deterministic, transition, std::vector< transition > >::type transitions_t
Definition: transition_map.hh:59
map_t & operator[](state_t s)
Definition: transition_map.hh:110
transition_map(const Aut &aut, const weightset_t &ws)
Definition: transition_map.hh:64
const Aut & aut_
The automaton whose transitions are cached.
Definition: transition_map.hh:120
transition_map(const Aut &aut)
Definition: transition_map.hh:69
WeightSet weightset_t
Definition: transition_map.hh:47
void insert_(map_t &map, label_t_of< Aut > l, transition t, typename std::enable_if< Deterministic_ >::type *=nullptr)
Insert l -> t in map.
Definition: transition_map.hh:76
std::map< label_t_of< Aut >, transitions_t > map_t
Definition: transition_map.hh:60
maps_t maps_
Definition: transition_map.hh:62
void insert_(map_t &map, label_t_of< Aut > l, transition t, typename std::enable_if<!Deterministic_ >::type *=nullptr)
Insert l -> t in map.
Definition: transition_map.hh:86
map_t & build_map_(typename maps_t::iterator lb, state_t s)
Build and return the transition map for state s, store at res.
Definition: transition_map.hh:96
std::map< state_t, map_t > maps_t
Definition: transition_map.hh:61
typename weightset_t::value_t weight_t
Definition: transition_map.hh:48
const weightset_t & ws_
The result weightset.
Definition: transition_map.hh:122
weight_t wgt
The (converted) weight.
Definition: transition_map.hh:52
state_t dst
Definition: transition_map.hh:53