Vcsn  2.2
Be Rational
epsilon-profile.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <tuple>
4 
5 namespace vcsn
6 {
7  namespace detail
8  {
10 
17  template <typename State>
19  {
20  using state_t = State;
21 
25  size_t in_sp;
27  size_t in_nsp;
29  size_t out_sp;
31  size_t out_nsp;
32 
41  size_t insp, size_t in,
42  size_t outsp, size_t out)
43  : state(s)
44  , in_sp(insp), in_nsp(in - insp)
45  , out_sp(outsp), out_nsp(out - outsp)
46  {}
47 
48  void update(size_t insp, size_t in,
49  size_t outsp, size_t out)
50  {
51  in_sp = insp;
52  in_nsp = in - insp;
53  out_sp = outsp;
54  out_nsp = out - outsp;
55  }
56 
61  bool operator<(const epsilon_profile& r) const
62  {
63  // (i) First, work on those with fewer outgoing spontaneous
64  // transitions.
65  // (ii) Prefer fewer outgoing transitions.
66  // (iii) Prefer fewer incoming spontaneous transitions.
67  // (iv) Then, ensure total order using state handle.
68  //
69  // Note the inversions between lhs and rhs.
70  return (std::tie (r.out_sp, r.out_nsp, r.in_sp, state)
71  < std::tie(out_sp, out_nsp, in_sp, r.state));
72  }
73 
74  friend std::ostream& operator<<(std::ostream& o, const epsilon_profile& p)
75  {
76  return o << p.state
77  << 'o' << p.out_sp
78  << 'O' << p.out_nsp
79  << 'i' << p.in_sp
80  << 'I' << p.in_nsp;
81  }
82  };
83  }
84 }
size_t in_sp
Number of incoming spontaneous transitions.
Definition: a-star.hh:8
bool operator<(const epsilon_profile &r) const
Whether l < r for the max-heap.
friend std::ostream & operator<<(std::ostream &o, const epsilon_profile &p)
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
state_t state
From the heap's top, recover state to eliminate.
size_t in_nsp
Number of incoming non-spontaneous transitions.
This is used by some epsilon removal algorithms.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
size_t out_nsp
Number of outgoing non-spontaneous transitions.
void update(size_t insp, size_t in, size_t outsp, size_t out)
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:105
epsilon_profile(state_t s, size_t insp, size_t in, size_t outsp, size_t out)
Generate a state profile.
size_t out_sp
Number of outgoing spontaneous transitions.