quotient.hh

Go to the documentation of this file.

#ifndef VCSN_ALGOS_QUOTIENT_HH
# define VCSN_ALGOS_QUOTIENT_HH

# include <algorithm> // min_element.
# include <unordered_map>
# include <unordered_set>

# include <vcsn/algos/accessible.hh>
# include <vcsn/algos/is-deterministic.hh>
# include <vcsn/core/partition-automaton.hh>
# include <vcsn/dyn/automaton.hh>
# include <vcsn/misc/dynamic_bitset.hh>

namespace vcsn
{

  namespace detail
  {
    template <typename Aut>
    class quotienter
    {
    public:
      using automaton_t = Aut;
      using partition_automaton_t = partition_automaton<automaton_t>;

      using class_t = unsigned;
      using state_t = state_t_of<automaton_t>;
      using set_t = std::vector<state_t>;
      using state_to_class_t = std::unordered_map<state_t, class_t>;
      using class_to_set_t = std::vector<set_t>;
      using class_to_state_t = std::vector<state_t>;

      quotienter(class_to_set_t& class_to_set)
        : class_to_set_(class_to_set)
        , num_classes_(class_to_set_.size())
      {
        sort_classes_();
      }

      void sort_classes_()
      {
        /* For each class, put its smallest numbered state first.  We
           don't need to fully sort.  */
        for (unsigned c = 0; c < num_classes_; ++c)
            std::swap(class_to_set_[c][0],
                      *std::min_element(begin(class_to_set_[c]),
                                        end(class_to_set_[c])));

        /* Sort class numbers by smallest state number.  */
        std::sort(begin(class_to_set_), end(class_to_set_),
                  [](const set_t& lhs, const set_t& rhs) -> bool
                  {
                    return lhs[0] < rhs[0];
                  });
      }

      partition_automaton_t build_result_(const automaton_t& aut)
      {
        state_to_class_t state_to_class;
        for (unsigned c = 0; c < num_classes_; ++c)
          for (auto s: class_to_set_[c])
            state_to_class[s] = c;

        partition_automaton_t res
          = make_shared_ptr<partition_automaton_t>(aut);
        class_to_res_state_.resize(num_classes_);
        for (unsigned c = 0; c < num_classes_; ++c)
          {
            const std::vector<state_t>& set = class_to_set_[c];
            state_t s = set[0];
            class_to_res_state_[c]
              = s == aut->pre()  ? res->pre()
              : s == aut->post() ? res->post()
              : res->new_state(set);
          }
        for (unsigned c = 0; c < num_classes_; ++c)
          {
            // Copy the transitions of the first state of the class in
            // the result.
            state_t s = class_to_set_[c][0];
            state_t src = class_to_res_state_[c];
            for (auto t : aut->all_out(s))
              {
                state_t d = aut->dst_of(t);
                state_t dst = class_to_res_state_[state_to_class[d]];
                res->add_transition(src, dst, aut->label_of(t), aut->weight_of(t));
              }
          }
        return std::move(res);
      }

      partition_automaton_t operator()(const automaton_t& aut)
      {
        return build_result_(aut);
      }

    private:
      std::ostream& print_(const set_t& ss, std::ostream& o) const
      {
        o << '{';
        const char* sep = "";
        for (auto s : ss)
          {
            o << sep << s;
            sep = ", ";
          }
        return o << '}';
      }
      std::ostream& print_(const class_to_set_t& c2ss, std::ostream& o) const
      {
        const char* sep = "";
        for (unsigned i = 0; i < c2ss.size(); ++i)
          {
            o << sep << '[' << i << "] = ";
            print_(c2ss[i], o);
            sep = "\n";
          }
        return o;
      }

    private:
      class_to_set_t& class_to_set_;
      unsigned num_classes_;
      class_to_state_t class_to_res_state_;
    };
  } // detail::

  template <typename Aut>
  inline
  auto
  quotient(const Aut& a,
           typename detail::quotienter<Aut>::class_to_set_t& classes)
    -> partition_automaton<Aut>
  {
    detail::quotienter<Aut> quotient(classes);
    return quotient(a);
  }

} // namespace vcsn

#endif // !VCSN_ALGOS_QUOTIENT_HH