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