Vcsn  2.2a
Be Rational
trie.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/dyn/automaton.hh>
6 #include <vcsn/dyn/context.hh>
7 #include <vcsn/dyn/polynomial.hh>
8 #include <vcsn/labelset/labelset.hh> // detail::letterized_context
10 #include <vcsn/misc/algorithm.hh> // front
11 #include <vcsn/misc/direction.hh>
12 #include <vcsn/misc/getargs.hh>
13 #include <vcsn/misc/regex.hh>
15 
16 namespace vcsn
17 {
18 
19  namespace detail
20  {
22  std::string quote(const std::string& s)
23  {
24  if (s == "\\e"
25  || (s.size() == 1 && std::isalnum(s[0])))
26  return s;
27  else
28  {
29  // Backslash backslashes and quotes.
30  static auto re = std::regex{"['\\\\ \\[\\]()+,|<>]"};
31  return std::regex_replace(s, re, "\\$&");
32  }
33  }
34 }
35 
36  /*--------------------.
37  | trie(polynomial). |
38  `--------------------*/
39  namespace detail
40  {
49  template <typename Context, direction Dir>
51  {
52  public:
53  using context_t = Context;
58  using work_automaton_t
59  = std::conditional_t<Dir == direction::forward,
69 
73  using monomial_t = typename polynomialset_t::monomial_t;
74 
77  {}
78 
82  void add(const word_t& l, const weight_t& w = weightset_t::one())
83  {
84  add_(l, w);
85  }
86 
88  void add(const monomial_t& m)
89  {
90  add(label_of(m), weight_of(m));
91  }
92 
94  void add(const polynomial_t& p)
95  {
96  for (const auto& m: p)
97  add(m);
98  }
99 
101  void add_words(std::istream& is)
102  {
103  auto ls = make_wordset(*ctx_.labelset());
104  ls.open(true);
105  std::string buf;
106  while (getline(is, buf))
107  {
108  auto w = conv(ls, quote(buf));
109  add(w);
110  }
111  }
112 
114  void add_monomials(std::istream& is)
115  {
116  auto ps = make_word_polynomialset(ctx_);
117  while (auto m = ps.conv_monomial(is))
118  add(*m);
119  }
120 
122  void add(std::istream& is, const std::string& format)
123  {
124  static const auto map = getarg<void(self_t::*)(std::istream&)>
125  {
126  "trie format",
127  {
128  {"default", "monomials"},
129  {"monomials", &self_t::add_monomials},
130  {"words", &self_t::add_words},
131  }
132  };
133  (this->*(map[format]))(is);
134  }
135 
137  template <direction D = Dir>
138  auto result()
139  -> std::enable_if_t<D == direction::forward, automaton_t>
140  {
141  return res_;
142  }
143 
145  template <direction D = Dir>
146  auto result()
147  -> std::enable_if_t<D == direction::backward, automaton_t>
148  {
149  return transpose(res_);
150  }
151 
152  private:
158  void add_(const word_t& lbl, const weight_t& wgt)
159  {
160  const auto& ls = *ctx_.labelset();
161  state_t s = res_->pre();
162  s = next_(s, ls.special());
163  for (auto l: ls.letters_of_padded(Dir == direction::forward
164  ? lbl
165  : ls.transpose(lbl),
166  padding_))
167  s = next_(s, l);
168  // The final transition, where we add the weight.
169  res_->add_transition(s, res_->post(), ls.special(), wgt);
170  }
171 
175  {
176  auto ts = out(res_, s, l);
177  assert(ts.size() == 0 || ts.size() == 1);
178  if (ts.empty())
179  {
180  auto d = res_->new_state();
181  res_->new_transition(s, d, l);
182  return d;
183  }
184  else
185  return res_->dst_of(front(ts));
186  }
187 
191  const context_t& ctx_ = res_->context();
195  };
196 
198  template <direction Dir, typename PolynomialSet>
200  make_trie_builder(const PolynomialSet& ps)
201  {
202  return {make_free_context(ps.context())};
203  }
204  }
205 
211  template <typename PolynomialSet>
213  trie(const PolynomialSet& ps, const typename PolynomialSet::value_t& p)
214  {
215  auto t = detail::make_trie_builder<direction::forward>(ps);
216  t.add(p);
217  return t.result();
218  }
219 
225  template <typename PolynomialSet>
226  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
227  cotrie(const PolynomialSet& ps, const typename PolynomialSet::value_t& p)
228  {
229  auto t = detail::make_trie_builder<direction::backward>(ps);
230  t.add(p);
231  return t.result();
232  }
233 
234  namespace dyn
235  {
236  namespace detail
237  {
239  template <typename PolynomialSet>
240  automaton
241  trie(const polynomial& poly)
242  {
243  const auto& p = poly->as<PolynomialSet>();
244  return make_automaton(trie(p.polynomialset(), p.polynomial()));
245  }
246 
248  template <typename PolynomialSet>
249  automaton
250  cotrie(const polynomial& poly)
251  {
252  const auto& p = poly->as<PolynomialSet>();
253  return make_automaton(cotrie(p.polynomialset(), p.polynomial()));
254  }
255  }
256  }
257 
258  /*--------------.
259  | trie(file). |
260  `--------------*/
261 
268  template <typename PolynomialSet>
269  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
270  trie(const PolynomialSet& ps, std::istream& is,
271  const std::string& format = "default")
272  {
273  auto t = detail::make_trie_builder<direction::forward>(ps);
274  t.add(is, format);
275  return t.result();
276  }
277 
284  template <typename PolynomialSet>
285  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
286  cotrie(const PolynomialSet& ps, std::istream& is,
287  const std::string& format = "default")
288  {
289  auto t = detail::make_trie_builder<direction::backward>(ps);
290  t.add(is, format);
291  return t.result();
292  }
293 
294  namespace dyn
295  {
296  namespace detail
297  {
299  template <typename Context, typename Istream, typename String>
300  automaton
301  trie_stream(const context& ctx, std::istream& is,
302  const std::string& format)
303  {
304  const auto& c = ctx->as<Context>();
305  auto ps = make_word_polynomialset(c);
306  return make_automaton(trie(ps, is, format));
307  }
308 
310  template <typename Context, typename Istream, typename String>
311  automaton
312  cotrie_stream(const context& ctx, std::istream& is,
313  const std::string& format)
314  {
315  const auto& c = ctx->as<Context>();
316  auto ps = make_word_polynomialset(c);
317  return make_automaton(cotrie(ps, is, format));
318  }
319  }
320  }
321 } // vcsn::
state_t next_(state_t s, letter_t l)
Follow a transition, possibly creating it.
Definition: trie.hh:174
mutable_automaton< context_t > automaton_t
The type of the result.
Definition: trie.hh:56
std::istringstream is
The input stream: the specification to translate.
Definition: translate.cc:380
letter_t_of< context_t > letter_t
Definition: trie.hh:64
constant< type_t::one, Context > one
Definition: fwd.hh:111
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
weightset_t_of< context_t > weightset_t
Definition: trie.hh:66
A mapping from strings to Values.
Definition: getargs.hh:33
labelset_t_of< context_t > labelset_t
The input labelset, free/letterized or not.
Definition: trie.hh:63
A dyn automaton.
Definition: automaton.hh:19
void add(const monomial_t &m)
Add a monomial.
Definition: trie.hh:88
std::shared_ptr< const detail::polynomial_base > polynomial
Definition: fwd.hh:53
mutable_automaton< detail::free_context< context_t_of< PolynomialSet > > > trie(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Make a trie-like mutable_automaton for a finite series given as a polynomial.
Definition: trie.hh:213
trie_builder< free_context< context_t_of< PolynomialSet > >, Dir > make_trie_builder(const PolynomialSet &ps)
Instantiate a trie-builder for this type of polynomialset.
Definition: trie.hh:200
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:269
void add(const polynomial_t &p)
Add a polynomial.
Definition: trie.hh:94
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
std::string quote(const std::string &s)
Turn a label into a parsable label: escape special characters.
Definition: trie.hh:22
typename polynomialset_t::monomial_t monomial_t
Definition: trie.hh:73
Looking downstream.
auto result() -> std::enable_if_t< D==direction::forward, automaton_t >
Get the result for the forward trie.
Definition: trie.hh:138
detail::automaton automaton
Definition: automaton.hh:108
auto conv(const ValueSet &vs, const std::string &str, Args &&...args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
Definition: stream.hh:28
state_t_of< automaton_t > state_t
Definition: trie.hh:68
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:82
std::conditional_t< Dir==direction::forward, automaton_t, transpose_automaton< automaton_t >> work_automaton_t
The type of the automaton we work on.
Definition: trie.hh:61
auto result() -> std::enable_if_t< D==direction::backward, automaton_t >
Get the result for a backward trie.
Definition: trie.hh:146
typename labelset_t_of< base_t< ValueSet >>::letter_t letter_t_of
Definition: traits.hh:78
word_t_of< context_t > word_t
Definition: trie.hh:65
std::shared_ptr< const detail::context_base > context
A dyn::context.
Definition: fwd.hh:26
trie_builder(const context_t &c)
Definition: trie.hh:75
mutable_automaton< detail::free_context< context_t_of< PolynomialSet > > > cotrie(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Make a cotrie-like mutable_automaton for a finite series given as a polynomial.
Definition: trie.hh:227
automaton trie_stream(const context &ctx, std::istream &is, const std::string &format)
Bridge (trie).
Definition: trie.hh:301
typename polynomialset_t::value_t polynomial_t
Definition: trie.hh:72
void add(const word_t &l, const weight_t &w=weightset_t::one())
Add a monomial.
Definition: trie.hh:82
void add_(const word_t &lbl, const weight_t &wgt)
Add a monomial.
Definition: trie.hh:158
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:160
auto make_word_polynomialset(const Ctx &ctx) -> word_polynomialset_t< Ctx >
The polynomialset of words of a labelset (not necessarily on words itself).
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:58
work_automaton_t res_
The automaton being built.
Definition: trie.hh:189
free_context< context< LabelSet, WeightSet > > make_free_context(const context< LabelSet, WeightSet > &c)
The free context for c.
Definition: labelset.hh:245
typename letterized_traits< LabelSet >::labelset_t letterized_t
Definition: labelset.hh:102
Build a trie automaton (prefix-tree-like automaton).
Definition: trie.hh:50
void add_monomials(std::istream &is)
Add all the monomials (one per line) in this stream.
Definition: trie.hh:114
std::shared_ptr< detail::transpose_automaton_impl< Aut >> transpose_automaton
An automaton wrapper that presents the transposed automaton.
Definition: fwd.hh:108
weight_t_of< context_t > weight_t
Definition: trie.hh:67
SharedPtr make_shared_ptr(Args &&...args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:14
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
letterized_t< labelset_t >::value_t padding_
Padding, in case it is needed.
Definition: trie.hh:194
automaton cotrie_stream(const context &ctx, std::istream &is, const std::string &format)
Bridge (cotrie).
Definition: trie.hh:312
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:113
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:39
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
void add_words(std::istream &is)
Add all the words (one per line) in this stream.
Definition: trie.hh:101
const context_t & ctx_
The context of the automaton: letterized.
Definition: trie.hh:191
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
void add(std::istream &is, const std::string &format)
Add all the monomials in this stream.
Definition: trie.hh:122
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:58
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:227
An input/output format for valuesets.
Definition: format.hh:11
Definition: a-star.hh:8