trie.hh

Go to the documentation of this file.

#pragma once

#include <vcsn/algos/transpose.hh>
#include <vcsn/core/mutable-automaton.hh>
#include <vcsn/dyn/automaton.hh>
#include <vcsn/dyn/context.hh>
#include <vcsn/dyn/polynomial.hh>
#include <vcsn/labelset/labelset.hh> // detail::letterized_context
#include <vcsn/labelset/word-polynomialset.hh>
#include <vcsn/misc/algorithm.hh> // front
#include <vcsn/misc/direction.hh>
#include <vcsn/misc/getargs.hh>
#include <vcsn/misc/regex.hh>
#include <vcsn/weightset/polynomialset.hh>

namespace vcsn
{

  namespace detail
  {
    std::string quote(const std::string& s)
    {
      if (s == "\\e"
          || (s.size() == 1 && std::isalnum(s[0])))
        return s;
      else
        {
          // Backslash backslashes and quotes.
          static auto re = std::regex{"['\\\\ \\[\\]()+,|<>]"};
          return std::regex_replace(s, re, "\\$&");
        }
    }
}

  /*--------------------.
  | trie(polynomial).   |
  `--------------------*/
  namespace detail
  {
    template <typename Context, direction Dir>
    class trie_builder
    {
    public:
      using context_t = Context;
      using self_t = trie_builder;
      using automaton_t = mutable_automaton<context_t>;
      using work_automaton_t
        = std::conditional_t<Dir == direction::forward,
                        automaton_t,
                        transpose_automaton<automaton_t>>;
      using labelset_t = labelset_t_of<context_t>;
      using letter_t = letter_t_of<context_t>;
      using word_t = word_t_of<context_t>;
      using weightset_t = weightset_t_of<context_t>;
      using weight_t = weight_t_of<context_t>;
      using state_t = state_t_of<automaton_t>;

      using polynomialset_t = word_polynomialset_t<context_t>;
      using polynomial_t = typename polynomialset_t::value_t;
      using monomial_t = typename polynomialset_t::monomial_t;

      trie_builder(const context_t& c)
        : res_(make_shared_ptr<work_automaton_t>(c))
      {}

      void add(const word_t& l, const weight_t& w = weightset_t::one())
      {
        add_(l, w);
      }

      void add(const monomial_t& m)
      {
        add(label_of(m), weight_of(m));
      }

      void add(const polynomial_t& p)
      {
        for (const auto& m: p)
          add(m);
      }

      void add_words(std::istream& is)
      {
        auto ls = make_wordset(*ctx_.labelset());
        ls.open(true);
        std::string buf;
        while (getline(is, buf))
          {
            auto w = conv(ls, quote(buf));
            add(w);
          }
      }

      void add_monomials(std::istream& is)
      {
        auto ps = make_word_polynomialset(ctx_);
        while (auto m = ps.conv_monomial(is))
          add(*m);
      }

      void add(std::istream& is, const std::string& format)
      {
        static const auto map = getarg<void(self_t::*)(std::istream&)>
          {
            "trie format",
            {
              {"default",   "monomials"},
              {"monomials", &self_t::add_monomials},
              {"words",     &self_t::add_words},
            }
          };
        (this->*(map[format]))(is);
      }

      template <direction D = Dir>
      auto result()
        -> std::enable_if_t<D == direction::forward, automaton_t>
      {
        return res_;
      }

      template <direction D = Dir>
      auto result()
        -> std::enable_if_t<D == direction::backward, automaton_t>
      {
        return transpose(res_);
      }

    private:
      void add_(const word_t& lbl, const weight_t& wgt)
      {
        const auto& ls = *ctx_.labelset();
        state_t s = res_->pre();
        s = next_(s, ls.special());
        for (auto l: ls.letters_of_padded(Dir == direction::forward
                                          ? lbl
                                          : ls.transpose(lbl),
                                          padding_))
          s = next_(s, l);
        // The final transition, where we add the weight.
        res_->add_transition(s, res_->post(), ls.special(), wgt);
      }

      state_t next_(state_t s, letter_t l)
      {
        auto ts = out(res_, s, l);
        assert(ts.size() == 0 || ts.size() == 1);
        if (ts.empty())
          {
            auto d = res_->new_state();
            res_->new_transition(s, d, l);
            return d;
          }
        else
          return res_->dst_of(front(ts));
      }

      work_automaton_t res_;
      const context_t& ctx_ = res_->context();
      typename letterized_t<labelset_t>::value_t padding_
        = letterized_t<labelset_t>::one();
    };

    template <direction Dir, typename PolynomialSet>
    trie_builder<free_context<context_t_of<PolynomialSet>>, Dir>
    make_trie_builder(const PolynomialSet& ps)
    {
      return {make_free_context(ps.context())};
    }
  }

  template <typename PolynomialSet>
  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
  trie(const PolynomialSet& ps, const typename PolynomialSet::value_t& p)
  {
    auto t = detail::make_trie_builder<direction::forward>(ps);
    t.add(p);
    return t.result();
  }

  template <typename PolynomialSet>
  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
  cotrie(const PolynomialSet& ps, const typename PolynomialSet::value_t& p)
  {
    auto t = detail::make_trie_builder<direction::backward>(ps);
    t.add(p);
    return t.result();
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename PolynomialSet>
      automaton
      trie(const polynomial& poly)
      {
        const auto& p = poly->as<PolynomialSet>();
        return make_automaton(trie(p.polynomialset(), p.polynomial()));
      }

      template <typename PolynomialSet>
      automaton
      cotrie(const polynomial& poly)
      {
        const auto& p = poly->as<PolynomialSet>();
        return make_automaton(cotrie(p.polynomialset(), p.polynomial()));
      }
    }
  }

  /*--------------.
  | trie(file).   |
  `--------------*/

  template <typename PolynomialSet>
  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
  trie(const PolynomialSet& ps, std::istream& is,
       const std::string& format = "default")
  {
    auto t = detail::make_trie_builder<direction::forward>(ps);
    t.add(is, format);
    return t.result();
  }

  template <typename PolynomialSet>
  mutable_automaton<detail::free_context<context_t_of<PolynomialSet>>>
  cotrie(const PolynomialSet& ps, std::istream& is,
         const std::string& format = "default")
  {
    auto t = detail::make_trie_builder<direction::backward>(ps);
    t.add(is, format);
    return t.result();
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename Context, typename Istream, typename String>
      automaton
      trie_stream(const context& ctx, std::istream& is,
                  const std::string& format)
      {
        const auto& c = ctx->as<Context>();
        auto ps = make_word_polynomialset(c);
        return make_automaton(trie(ps, is, format));
      }

      template <typename Context, typename Istream, typename String>
      automaton
      cotrie_stream(const context& ctx, std::istream& is,
                    const std::string& format)
      {
        const auto& c = ctx->as<Context>();
        auto ps = make_word_polynomialset(c);
        return make_automaton(cotrie(ps, is, format));
      }
    }
  }
} // vcsn::