random-expression.hh

Go to the documentation of this file.

#include <ostream>
#include <regex>
#include <string>

#include <boost/algorithm/string/erase.hpp>
#include <boost/tokenizer.hpp>

#include <vcsn/core/rat/expressionset.hh> // make_expressionset
#include <vcsn/dyn/algos.hh>
#include <vcsn/misc/algorithm.hh>
#include <vcsn/misc/cast.hh>
#include <vcsn/misc/raise.hh>
#include <vcsn/misc/random.hh>
#include <vcsn/misc/unordered_map.hh>

namespace vcsn
{
  namespace detail
  {

    template <typename ExpressionSet,
              typename RandomGenerator = std::default_random_engine>
    class random_expression_impl
    {
    public:
      using expressionset_t = ExpressionSet;
      using expression_t    = typename expressionset_t::value_t;
      using weight_t        = typename expressionset_t::weight_t;
      using weightset_t     = typename expressionset_t::weightset_t;

      random_expression_impl(const expressionset_t& rs,
                             const std::string& param,
                             RandomGenerator& gen)
        : rs_{rs}
        , gen_{gen}
      {
        parse_param_(param);
      }

      std::ostream& print_random_expression(std::ostream& out) const
      {
        return print_random_expression_(out, length_);
      }

      std::string random_expression_string() const
      {
        std::ostringstream out;
        print_random_expression(out);
        return out.str();
      }

      expression_t random_expression() const
      {
        return conv(rs_, random_expression_string());
      }

    private:
      void parse_param_(const std::string& param)
      {
        // Set default value.
        length_ = 6;
        using tokenizer = boost::tokenizer<boost::escaped_list_separator<char>>;
        using boost::algorithm::erase_all_copy;
        auto sep = boost::escaped_list_separator<char>("#####", ",", "\"");
        for (const auto& arg: tokenizer(param, sep))
        {
          auto eq = arg.find('=');
          auto op = erase_all_copy(arg.substr(0, eq), " ");
          if (op == "w")
            random_weight_.parse_param(arg.substr(eq + 1));
          else
          {
            float value = (eq != std::string::npos)
              ? detail::lexical_cast<float>(arg.substr(eq + 1))
              : 1;
            if (has(arities_, op))
              operators_[op] = value;
            else if (op == "length")
              length_ = value;
            else
              raise("random_expression: invalid operator: ", op);
          }
        }
        proba_op_ = transform(operators_,
                              [](const auto& v){ return v.second; });
      }

      void print_weight_(std::ostream& out) const
      {
        out << "<";
        rs_.weightset()->print(random_weight_.generate_random_weight(), out);
        out << ">";
      }

      void print_label_(std::ostream& out) const
      {
        rs_.labelset()->print(random_label(*rs_.labelset(), gen_), out);
      }

      void print_unary_exp_(std::ostream& out, unsigned length,
                            const std::string& op) const
      {
        // Prefix.
        if (op == "!" || op == "w.")
        {
          out << '(';
          if (op == "w.")
            print_weight_(out);
          else
            out << op;
          print_random_expression_(out, length - 1);
          out << ')';
        }
        // Postfix.
        else
        {
          out << '(';
          print_random_expression_(out, length - 1);
          if (op == ".w")
            print_weight_(out);
          else
            out << op;
          out << ")";
        }
      }

      void print_binary_exp_(std::ostream& out, unsigned length,
                             const std::string& op) const
      {
        if (length < 3)
          print_label_(out);
        else
        {
          auto dis = std::uniform_int_distribution<>(1, length - 2);
          auto num_lhs = dis(gen_);
          out << "(";
          print_random_expression_(out, num_lhs);
          out << op;
          print_random_expression_(out, length - 1 - num_lhs);
          out << ")";
        }
      }

      std::ostream&
      print_random_expression_(std::ostream& out, unsigned length) const
      {
        // If there is no operators at all, that's impossible to
        // construct an expression, so just return a label.
        if (operators_.empty())
          print_label_(out);

        // One symbol left: print a label.
        else if (length == 1)
          print_label_(out);

        // All operators are possible, choose one randomly (with
        // associated weight probability) and print the associated
        // expression.
        else
        {
          // Choose an operator.
          auto op = chooser_it_(proba_op_, operators_)->first;
          switch (arities_.at(op))
            {
            case 0:
              out << op;
              break;
            case 1:
              print_unary_exp_(out, length, op);
              break;
            case 2:
              print_binary_exp_(out, length, op);
              break;
            default:
              assert(!"invalid arity");
            }
        }
        return out;
      }

      expressionset_t rs_;
      weightset_t ws_;
      unsigned length_;
      std::map<std::string, float> operators_;
      std::unordered_map<std::string, int> arities_
      {
        // Nullary.
        {"\\e", 0},
        {"\\z", 0},
        // Unary.
        {"!", 1},
        {"{c}", 1},
        {"*", 1},
        {"{T}", 1},
        {"w.", 1},
        {".w", 1},
        // Binary.
        {"&", 2},
        {"&:", 2},
        {":", 2},
        {".", 2},
        {"<+", 2},
        {"%", 2},
        {"+", 2},
        {"{/}", 2},
        {"{\\}",2},
      };

      std::vector<float> proba_op_;
      RandomGenerator& gen_;
      random_weight<weightset_t, RandomGenerator> random_weight_{gen_, ws_};
      discrete_chooser<RandomGenerator> chooser_it_{gen_};
    };

    template <typename ExpressionSet, typename RandomGenerator = std::mt19937>
    random_expression_impl<ExpressionSet, RandomGenerator>
    make_random_expression_impl(const ExpressionSet& rs,
                                const std::string& param,
                                RandomGenerator& gen = make_random_engine())
    {
      return {rs, param, gen};
    }

  } // end namespace vcsn::detail


  template <typename ExpressionSet>
  std::string
  random_expression_string(const ExpressionSet& rs, const std::string& param)
  {
    auto random_exp = detail::make_random_expression_impl(rs, param);
    return random_exp.random_expression_string();
  }


  template <typename ExpressionSet>
  typename ExpressionSet::value_t
  random_expression(const ExpressionSet& rs, const std::string& param)
  {
    auto random_exp = detail::make_random_expression_impl(rs, param);
    return random_exp.random_expression();
  }

  namespace dyn
  {
    namespace detail
    {
      template <typename Context, typename String, typename Identities>
      expression
      random_expression(const context& ctx, const std::string& param,
                        identities ids)
      {
        const auto& c = ctx->as<Context>();
        auto rs = make_expressionset(c, ids);
        return {rs, random_expression(rs, param)};
      }
    }
  }
} // end namespace vcsn