wordset.hh

Go to the documentation of this file.

#pragma once

#include <memory>

#include <boost/range/algorithm/mismatch.hpp>
#include <boost/algorithm/string/predicate.hpp> // starts_with
#include <boost/optional.hpp>

#include <vcsn/core/kind.hh>
#include <vcsn/labelset/fwd.hh>
#include <vcsn/labelset/genset-labelset.hh>
#include <vcsn/labelset/labelset.hh>
#include <vcsn/labelset/letterset.hh> // for letterized_traits
#include <vcsn/misc/attributes.hh>
#include <vcsn/misc/functional.hh>
#include <vcsn/misc/irange.hh>
#include <vcsn/misc/raise.hh>

namespace vcsn
{
  template <typename GenSet>
  class wordset: public detail::genset_labelset<GenSet>
  {
  public:
    using genset_t = GenSet;
    using super_t = detail::genset_labelset<genset_t>;
    using self_t = wordset;
    using genset_ptr = std::shared_ptr<const genset_t>;

    using letter_t = typename genset_t::letter_t;
    using word_t = typename genset_t::word_t;

    using value_t = word_t;

    using kind_t = labels_are_words;

    wordset(const genset_ptr& gs)
      : super_t{gs}
    {}

    wordset(const genset_t& gs = {})
      : wordset{std::make_shared<const genset_t>(gs)}
    {}

    wordset(std::initializer_list<letter_t> letters)
      : wordset(std::make_shared<const genset_t>(letters))
    {}

    static symbol sname()
    {
      static auto res = symbol{"wordset<" + super_t::sname() + '>'};
      return res;
    }

    static wordset make(std::istream& is)
    {
      // name: wordset<char_letters(abc)>.
      //       ^^^^^^^ ^^^^^^^^^^^^^^^^^
      //         kind      genset
      eat(is, "wordset<");
      auto gs = genset_t::make(is);
      eat(is, '>');
      return gs;
    }

    bool open(bool o) const
    {
      return this->genset()->open(o);
    }

    static constexpr bool is_free()
    {
      return false;
    }

    template <typename... Args>
    value_t value(Args&&... args) const
    {
      return value_t{std::forward<Args>(args)...};
    }

    word_t word(const value_t& v) const
    {
      return v;
    }

    static word_t
    letters_of(const value_t& v)
    {
      return v;
    }

    static word_t
    letters_of_padded(const value_t& v, letter_t)
    {
      return v;
    }

    static bool
    equal(const value_t& l, const value_t& r)
    {
      return l == r;
    }

    static bool less(const letter_t& l, const letter_t& r)
    {
      return genset_t::less(l, r);
    }

    static bool less(const value_t& l, const value_t& r)
    {
      // Be sure to use genset::less().
      auto s1 = size(l);
      auto s2 = size(r);
      if (s1 < s2)
        return true;
      else if (s2 < s1)
        return false;
      else
        return genset_t::less(l, r);
    }

    static value_t
    special()
    {
      return genset_t::template special<value_t>();
    }

    static bool
    is_special(const value_t& v)
    {
      return v == special();
    }

    bool
    is_valid(const value_t& v) const
    {
      for (auto l: v)
        if (!this->has(l))
          return false;
      return true;
    }

    static constexpr bool
    is_expressionset()
    {
      return false;
    }

    static constexpr bool
    has_one()
    {
      return true;
    }

    static constexpr bool
    is_letterized()
    {
      return false;
    }

    static value_t
    one()
    {
      return genset_t::empty_word();
    }

    static bool
    is_one(const value_t& l) ATTRIBUTE_PURE
    {
      return genset_t::is_empty_word(l);
    }

    static size_t size(const value_t& v)
    {
      // Not v.length(), because word_t can actually be a vector
      // (e.g., with string_letters).
      return v.size();
    }

    static size_t hash(const value_t& v)
    {
      return hash_value(v);
    }

    value_t
    conv(self_t, const value_t& v) const
    {
      return v;
    }

    template <typename GenSet_>
    value_t
    conv(const letterset<GenSet_>& ls,
         typename letterset<GenSet_>::value_t v) const
    {
      if (ls.is_special(v))
        return special();
      else
        {
          auto res = value(v);
          VCSN_REQUIRE(is_valid(res),
                       *this, ": conv: invalid label: ", str_escape(v));
          return res;
        }
    }

    template <typename LabelSet_>
    value_t
    conv(const nullableset<LabelSet_>& ls,
         const typename nullableset<LabelSet_>::value_t& v) const
    {
      if (ls.is_one(v))
        return one();
      else
        return conv(*ls.labelset(), ls.get_value(v));
    }

    value_t
    conv(std::istream& i, bool = true) const
    {
      return this->genset()->get_word(i);
    }

    template <typename Fun>
    void convs(std::istream& i, Fun fun) const
    {
      this->convs_(i, [this,fun](letter_t l) { fun(value(l)); });
    }

    std::ostream&
    print(const value_t& l, std::ostream& o = std::cout,
          format fmt = {}) const
    {
      if (is_one(l))
        o << (fmt == format::latex ? "\\varepsilon"
              : fmt == format::utf8 ? "ε"
              : "\\e");
      else if (!is_special(l))
        this->genset()->print(l, o, fmt);
      return o;
    }

    std::ostream&
    print_set(std::ostream& o, format fmt = {}) const
    {
      switch (fmt.kind())
        {
        case format::latex:
          this->genset()->print_set(o, fmt);
          o << "^*";
          break;
        case format::sname:
          o << "wordset<";
          this->genset()->print_set(o, fmt);
          o << '>';
          break;
        case format::text:
        case format::utf8:
          this->genset()->print_set(o, fmt);
          o << '*';
          break;
        case format::raw:
          assert(0);
          break;
        }
      return o;
    }

    static value_t lgcd(const value_t& w1, const value_t& w2)
    {
      return {w1.begin(), boost::mismatch(w1, w2).first};
    }

    value_t ldivide(const value_t& w1, const value_t& w2) const
    {
      auto res = maybe_ldivide(w1, w2);
      VCSN_REQUIRE(res,
                   *this, ": ldivide: invalid arguments: ",
                   to_string(*this, w1),
                   ", ", to_string(*this, w2));
      return *res;
    }

    boost::optional<value_t>
    maybe_ldivide(const value_t& w1, const value_t& w2) const
    {
      using boost::algorithm::starts_with;
      if (starts_with(w2, w1))
        return value_t{begin(w2) + size(w1), end(w2)};
      else
        return boost::none;
    }

    value_t& ldivide_here(const value_t& w1, value_t& w2) const
    {
      w2 = ldivide(w1, w2);
      return w2;
    }

    value_t rdivide(const value_t& w1, const value_t& w2) const
    {
      auto res = maybe_rdivide(w1, w2);
      VCSN_REQUIRE(res,
                   *this, ": rdivide: invalid arguments: ",
                   to_string(*this, w1),
                   ", ", to_string(*this, w2));
      return *res;
    }

    boost::optional<value_t>
    maybe_rdivide(const value_t& w1, const value_t& w2) const
    {
      using boost::algorithm::ends_with;
      if (ends_with(w1, w2))
        return value_t{begin(w1), end(w1) - size(w2)};
      else
        return boost::none;
    }

    value_t& rdivide_here(value_t& w1, const value_t& w2) const
    {
      w1 = rdivide(w1, w2);
      return w1;
    }

    const value_t& conjunction(const value_t& l, const value_t& r) const
    {
      if (equal(l, r))
        return l;
      else
        raise(*this,
              ": conjunction: invalid operation (lhs and rhs are not equal): ",
              to_string(*this, l), ", ", to_string(*this, r));
    }
  };

  namespace detail
  {
    template <typename GenSet>
    struct letterized_traits<wordset<GenSet>>
    {
      static constexpr bool is_letterized = false;

      using labelset_t = nullableset<letterset<GenSet>>;

      static labelset_t labelset(const wordset<GenSet>& ls)
      {
        return {ls.genset()};
      }
    };

    template <typename GenSet>
    struct nullableset_traits<wordset<GenSet>>
    {
      using type = wordset<GenSet>;
      static type value(const wordset<GenSet>& ls)
      {
        return ls;
      }
    };

    template <typename GenSet>
    struct law_traits<wordset<GenSet>>
    {
      using type = wordset<GenSet>;
      static type value(const wordset<GenSet>& ls)
      {
        return ls;
      }
    };

    /*-------.
    | Join.  |
    `-------*/

#define DEFINE(Lhs, Rhs)                                  \
    template <typename GenSet>                            \
    struct join_impl<Lhs, Rhs>                            \
    {                                                     \
      using type = Rhs;                                   \
      static type join(const Lhs& lhs, const Rhs& rhs)    \
      {                                                   \
        return {set_union(*lhs.genset(), *rhs.genset())}; \
      }                                                   \
    }

    DEFINE(letterset<GenSet>,              wordset<GenSet>);
    DEFINE(nullableset<letterset<GenSet>>, wordset<GenSet>);
    DEFINE(wordset<GenSet>,                wordset<GenSet>);
#undef DEFINE
  }

  // FIXME: Factor in genset_labelset?
  template <typename GenSet>
  wordset<GenSet>
  meet(const wordset<GenSet>& lhs, const wordset<GenSet>& rhs)
  {
    return {set_intersection(*lhs.genset(), *rhs.genset())};
  }


  /*----------------.
  | random_label.   |
  `----------------*/

  template <typename GenSet,
            typename RandomGenerator = std::default_random_engine>
  typename wordset<GenSet>::value_t
  random_label(const wordset<GenSet>& ls,
               RandomGenerator& gen = RandomGenerator())
  {
    require(!ls.generators().empty(),
            "random_label: the alphabet needs at least 1 letter");
    auto dis = std::uniform_int_distribution<>(0, 5);
    auto res_label = ls.one();
    auto pick = make_random_selector(gen);
    for (auto _: detail::irange(dis(gen)))
      res_label = ls.mul(res_label, ls.value(pick(ls.generators())));
    return res_label;
  }
}