Vcsn  2.4
Be Rational
transition-map.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <type_traits>
4 #include <vector>
5 
7 #include <vcsn/misc/map.hh> // vcsn::less
8 
9 namespace vcsn
10 {
11  namespace detail
12  {
13 
30  template <Automaton Aut,
31  typename WeightSet = weightset_t_of<Aut>,
32  bool Deterministic = false,
33  bool AllOut = false,
34  bool KeepTransitions = false>
36  {
37  public:
42  using weightset_t = WeightSet;
43  using weight_t = typename weightset_t::value_t;
44 
46  template <typename Weight = weight_t,
47  bool KeepTransitions_ = false, typename Dummy = void>
48  struct transition_
49  {
51  : wgt(w)
52  , dst(d)
53  {}
56  weight_t weight() const { return wgt; }
58  };
59 
61  template <typename Dummy>
62  struct transition_<bool, false, Dummy>
63  {
65  : dst(d)
66  {}
67  static constexpr weight_t weight() { return true; }
69  };
70 
73  template <typename Weight, typename Dummy>
74  struct transition_<Weight, true, Dummy>
75  {
77  : wgt(w), dst(d), transition(t)
78  {}
81  weight_t weight() const { return wgt; }
84  };
85 
88  template <typename Dummy>
89  struct transition_<bool, true, Dummy>
90  {
92  : dst(d), transition(t)
93  {}
94  static constexpr bool weight() { return true; }
97  };
98 
101  using transition = transition_<weight_t, KeepTransitions>;
102 
103  using transitions_t
104  = std::conditional_t<Deterministic,
105  transition,
106  std::vector<transition>>;
107  using map_t = std::map<label_t_of<Aut>, transitions_t,
109 
110  transition_map(const Aut& aut, const weightset_t& ws)
111  : maps_(states_size(aut))
112  , aut_(aut)
113  , ws_(ws)
114  {}
115 
116  transition_map(const Aut& aut)
117  : transition_map(aut, *aut->weightset())
118  {}
119 
121  : maps_(std::move(that.maps_))
122  , aut_(std::move(that.aut_))
123  , ws_(that.ws_)
124  {}
125 
128  {
129  // We might be working on a lazy automaton, so be prepared to
130  // find states that did not exist when we created this
131  // transition map.
132  if (maps_.size() <= s)
133  {
134  auto capacity = maps_.capacity();
135  while (capacity <= s)
136  capacity *= 2;
137  maps_.reserve(capacity);
138  maps_.resize(s + 1);
139  }
140  auto& res = maps_[s];
141  if (!res)
142  {
143  res = std::make_unique<map_t>();
144  build_map_(*res, s);
145  }
146  return *res;
147  }
148 
149  private:
151  using maps_t = std::vector<std::unique_ptr<map_t>>;
152 
154  template <bool Deterministic_>
155  void
157  label_t_of<Aut> l, transition t,
158  std::enable_if_t<Deterministic_>* = nullptr)
159  {
160  map.emplace(l, t);
161  }
162 
164  template <bool Deterministic_>
165  void
167  label_t_of<Aut> l, transition t,
168  std::enable_if_t<!Deterministic_>* = nullptr)
169  {
170  map[l].emplace_back(t);
171  }
172 
174  void
176  {
177  for (auto t: all_out(aut_, s))
178  if (AllOut || !aut_->labelset()->is_special(aut_->label_of(t)))
179  {
180  auto w = ws_.conv(*aut_->weightset(), aut_->weight_of(t));
181  insert_<Deterministic>(map,
182  aut_->label_of(t),
183  transition{w, aut_->dst_of(t), t});
184  }
185  }
186 
190  Aut aut_;
192  const weightset_t& ws_;
193  };
194  }
195 }
STL namespace.
return res
Definition: multiply.hh:398
Aut aut_
The automaton whose transitions are cached.
Functor to compare Values of ValueSets.
Definition: functional.hh:76
Outgoing signature: weight, destination.
transition_< weight_t, false > transition
Outgoing signature: weight, destination, and possibly transition identifier.
#define Automaton
Definition: automaton.hh:23
std::conditional_t< Deterministic, transition, std::vector< transition >> transitions_t
const weightset_t & ws_
The result weightset.
weight_t wgt
The (converted) weight.
void insert_(map_t &map, label_t_of< Aut > l, transition t, std::enable_if_t< Deterministic_ > *=nullptr)
Insert l -> t in map.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
transition_(weight_t w, state_t d, transition_t)
map_t & operator[](state_t s)
Outgoing transitions of state s, sorted by label.
std::map< label_t_of< Aut >, transitions_t, less< labelset_t_of< Aut >>> map_t
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:40
void insert_(map_t &map, label_t_of< Aut > l, transition t, std::enable_if_t<!Deterministic_ > *=nullptr)
Insert l -> t in map.
Definition: a-star.hh:8
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
Cache the outgoing transitions of an automaton as efficient maps label -> vector<(weight, dst)>.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
std::vector< std::unique_ptr< map_t >> maps_t
For each state number, its transition map.
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:177
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
transition_map(transition_map &&that)
transition_map(const Aut &aut, const weightset_t &ws)
void build_map_(map_t &map, state_t s)
Build the transition map for state s, store at map.