mutable-automaton.hh

Go to the documentation of this file.

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>

#include <boost/range/algorithm/find.hpp>
#include <boost/range/algorithm/find_if.hpp>
#include <boost/range/irange.hpp>

#include <vcsn/concepts/automaton.hh>
#include <vcsn/core/fwd.hh>
#include <vcsn/core/transition.hh>
#include <vcsn/ctx/context.hh>
#include <vcsn/ctx/traits.hh>
#include <vcsn/misc/crange.hh>
#include <vcsn/misc/format.hh>
#include <vcsn/misc/index.hh>
#include <vcsn/misc/memory.hh>
#include <vcsn/misc/symbol.hh>

namespace vcsn
{
  namespace detail
  {
  template <typename Context>
  class mutable_automaton_impl
  {
  public:
    using context_t = Context;
    using self_t = mutable_automaton_impl;
    template <typename Ctx = Context>
    using fresh_automaton_t = mutable_automaton<Ctx>;
    using labelset_t = labelset_t_of<context_t>;
    using weightset_t = weightset_t_of<context_t>;
    using kind_t = typename context_t::kind_t;

    using labelset_ptr = typename context_t::labelset_ptr;
    using weightset_ptr = typename context_t::weightset_ptr;

    struct state_tag {};
    using state_t = index_t_impl<state_tag>;
    struct transition_tag {};
    using transition_t = index_t_impl<transition_tag>;
    using label_t = typename labelset_t::value_t;
    using weight_t = typename weightset_t::value_t;

  protected:
    context_t ctx_;

    using stored_transition_t = transition_tuple<state_t, label_t, weight_t>;

    using tr_store_t = std::vector<stored_transition_t>;
    using tr_cont_t = std::vector<transition_t>;

    struct stored_state_t
    {
      tr_cont_t succ;
      tr_cont_t pred;
    };

    using st_store_t = std::vector<stored_state_t>;

    using free_store_t = std::vector<unsigned>;

    st_store_t states_;
    free_store_t states_fs_;
    tr_store_t transitions_;
    free_store_t transitions_fs_;
    label_t prepost_label_;

  public:
    mutable_automaton_impl() = delete;
    mutable_automaton_impl(const mutable_automaton_impl&) = delete;
    mutable_automaton_impl(const context_t& ctx)
      : ctx_{ctx}
      , states_{2}
      , prepost_label_(ctx.labelset()->special())
    {}

    mutable_automaton_impl(mutable_automaton_impl&& that)
      : ctx_(that.ctx_)
      , prepost_label_(that.prepost_label_)
    {
      *this = std::move(that);
    }

    mutable_automaton_impl& operator=(mutable_automaton_impl&& that)
    {
      if (this != &that)
        {
          ctx_ = std::move(that.ctx_);
          prepost_label_ = std::move(that.prepost_label_);
          std::swap(states_, that.states_);
          std::swap(states_fs_, that.states_fs_);
          std::swap(transitions_, that.transitions_);
          std::swap(transitions_fs_, that.transitions_fs_);
        }
      return *this;
    }


    /*----------------.
    | Related sets.   |
    `----------------*/

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

    std::ostream& print_set(std::ostream& o = std::cout, format fmt = {}) const
    {
      o << "mutable_automaton<";
      context().print_set(o, fmt);
      return o << '>';
    }

    const context_t& context() const { return ctx_; }
    const weightset_ptr& weightset() const { return ctx_.weightset(); }
    const labelset_ptr& labelset() const { return ctx_.labelset(); }


    /*----------------------------------.
    | Special states and transitions.   |
    `----------------------------------*/

    // pseudo-initial and final states.
    // The code below assumes that pre() and post() are the first
    // two states of the automaton.  In other words, all other states
    // have greater numbers.  We also assume that pre()<post().
    static constexpr state_t      pre()  { return 0U; }
    static constexpr state_t      post()  { return 1U; }
    static constexpr state_t      null_state()      { return -1U; }
    static constexpr transition_t null_transition() { return -1U; }
    static constexpr transition_t lazy_transition() { return -2U; }

    label_t prepost_label() const
    {
      return prepost_label_;
    }


    /*--------------.
    | Statistics.   |
    `--------------*/

    size_t num_all_states() const { return states_.size() - states_fs_.size(); }
    size_t num_states() const { return num_all_states() - 2; }
    size_t num_initials() const { return states_[pre()].succ.size(); }
    size_t num_finals() const { return states_[post()].pred.size(); }
    size_t num_transitions() const
    {
      return (transitions_.size()
              - transitions_fs_.size() - num_initials() - num_finals());
    }


    /*---------------------.
    | Queries on states.   |
    `---------------------*/

    bool
    has_state(state_t s) const
    {
      // Any number outside our container is not a state.
      // (This includes "null_state()".)
      if (states_.size() <= s)
        return false;
      else
        {
          const stored_state_t& ss = states_[s];
          // Erased states have 'invalid' as their first successor.
          return ss.succ.empty() || ss.succ.front() != null_transition();
        }
    }

    bool
    is_lazy(state_t s) const
    {
      auto ts = all_out(s);
      return !ts.empty() && ts.front() == lazy_transition();
    }

    bool
    is_lazy_in(state_t s) const
    {
      auto ts = all_in(s);
      return !ts.empty() && ts.front() == lazy_transition();
    }

    bool
    is_initial(state_t s) const
    {
      return has_transition(pre(), s, prepost_label_);
    }

    bool
    is_final(state_t s) const
    {
      return has_transition(s, post(), prepost_label_);
    }

    ATTRIBUTE_PURE
    weight_t
    get_initial_weight(state_t s) const
    {
      transition_t t = get_transition(pre(), s, prepost_label_);
      if (t == null_transition())
        return weightset()->zero();
      else
        return weight_of(t);
    }

    ATTRIBUTE_PURE
    weight_t
    get_final_weight(state_t s) const
    {
      transition_t t = get_transition(s, post(), prepost_label_);
      if (t == null_transition())
        return weightset()->zero();
      else
        return weight_of(t);
    }


    /*--------------------------.
    | Queries on transitions.   |
    `--------------------------*/

    transition_t
    get_transition(state_t src, state_t dst, label_t l) const
    {
      assert(has_state(src));
      assert(!is_lazy(src));
      assert(has_state(dst));
      assert(!is_lazy_in(dst));
      const tr_cont_t& succ = states_[src].succ;
      const tr_cont_t& pred = states_[dst].pred;
      const auto& ls = *this->labelset();
      if (succ.size() <= pred.size())
        {
          auto i =
            boost::find_if(succ,
                           [this,l,ls,dst] (transition_t t)
                           {
                             return (dst_of(t) == dst
                                     && ls.equal(label_of(t), l));
                           });
          if (i != end(succ))
            return *i;
        }
      else
        {
          auto i =
            boost::find_if(pred,
                           [this,l,ls,src] (transition_t t)
                           {
                             return (src_of(t) == src
                                     && ls.equal(label_of(t), l));
                           });
          if (i != end(pred))
            return *i;
        }
      return null_transition();
    }

    bool
    has_transition(state_t src, state_t dst, label_t l) const
    {
      return get_transition(src, dst, l) != null_transition();
    }

    bool
    has_transition(transition_t t) const
    {
      // Any number outside our container is not a transition.
      // (This includes "null_transition()".)
      if (t >= transitions_.size())
        return false;

      // Erased transition have invalid source state.
      return transitions_[t].src != null_state();
    }

    state_t src_of(transition_t t) const   { return transitions_[t].src; }
    state_t dst_of(transition_t t) const   { return transitions_[t].dst; }
    label_t label_of(transition_t t) const
    {
      return transitions_[t].get_label();
    }

    weight_t weight_of(transition_t t) const
    {
      return transitions_[t].get_weight();
    }


    /*---------------------.
    | Edition of states.   |
    `---------------------*/

  protected:
    void
    del_transition_from_src(transition_t t)
    {
      stored_transition_t& st = transitions_[t];
      auto& succ = states_[st.src].succ;
      auto tsucc = boost::range::find(succ, t);
      assert(tsucc != succ.end());
      *tsucc = std::move(succ.back());
      succ.pop_back();
    }

    void
    del_transition_from_dst(transition_t t)
    {
      stored_transition_t& st = transitions_[t];
      auto& pred = states_[st.dst].pred;
      auto tpred = boost::range::find(pred, t);
      assert(tpred != pred.end());
      *tpred = std::move(pred.back());
      pred.pop_back();
    }

    void
    del_transition_container(tr_cont_t& tc, bool from_succ)
    {
      for (auto t: tc)
        {
          if (from_succ)
            del_transition_from_dst(t);
          else
            del_transition_from_src(t);
          transitions_[t].src = null_state();
        }
      transitions_fs_.insert(transitions_fs_.end(), tc.begin(), tc.end());
      tc.clear();
    }

  public:
    state_t
    new_state()
    {
      state_t res;
      if (states_fs_.empty())
        {
          res = states_.size();
          states_.emplace_back();
        }
      else
        {
          res = states_fs_.back();
          states_fs_.pop_back();
          stored_state_t& ss = states_[res];
          // De-invalidate this state: remove the invalid transition.
          ss.succ.clear();
        }
      return res;
    }

    std::ostream&
    print_state(state_t s, std::ostream& o = std::cout) const
    {
      if (s == pre())
        o << "pre";
      else if (s == post())
        o << "post";
      else
        o << s - 2;
      return o;
    }

    std::ostream&
    print_state_name(state_t s, std::ostream& o = std::cout,
                     format = {},
                     bool = false) const
    {
      return print_state(s, o);
    }

    static constexpr bool
    state_has_name(state_t)
    {
      return false;
    }

    void
    del_state(state_t s)
    {
      assert(has_state(s));
      assert(s > post()); // Cannot erase pre() and post().
      stored_state_t& ss = states_[s];
      del_transition_container(ss.pred, false);
      del_transition_container(ss.succ, true);
      ss.succ.emplace_back(null_transition()); // So has_state() can work.
      states_fs_.emplace_back(s);
    }

    transition_t
    set_initial(state_t s, weight_t w)
    {
      return set_transition(pre(), s, prepost_label_, w);
    }

    transition_t
    set_initial(state_t s)
    {
      return set_initial(s, weightset()->one());
    }

    void
    set_lazy(state_t s, bool lazy = true)
    {
      assert(has_state(s));
      stored_state_t& ss = states_[s];
      assert(ss.succ.empty()
             || ss.succ.front() == lazy_transition());
      ss.succ.clear();
      if (lazy)
        ss.succ.emplace_back(lazy_transition());
    }

    void
    set_lazy_in(state_t s, bool lazy = true)
    {
      assert(has_state(s));
      stored_state_t& ss = states_[s];
      assert(ss.pred.empty()
             || ss.pred.front() == lazy_transition());
      ss.pred.clear();
      if (lazy)
        ss.pred.emplace_back(lazy_transition());
    }

    transition_t
    add_initial(state_t s, weight_t w)
    {
      return add_transition(pre(), s, prepost_label_, w);
    }

    void
    unset_initial(state_t s)
    {
      set_initial(s, weightset()->zero());
    }

    transition_t
    set_final(state_t s, weight_t w)
    {
      return set_transition(s, post(), prepost_label_, w);
    }

    transition_t
    set_final(state_t s)
    {
      return set_final(s, weightset()->one());
    }

    transition_t
    add_final(state_t s, weight_t w)
    {
      return add_transition(s, post(), prepost_label_, w);
    }

    void
    unset_final(state_t s)
    {
      set_final(s, weightset()->zero());
    }


    /*--------------------------.
    | Edition of transitions.   |
    `--------------------------*/

    void
    del_transition(transition_t t)
    {
      assert(has_transition(t));
      // Remove transition from source and destination.
      del_transition_from_src(t);
      del_transition_from_dst(t);
      // Actually erase the transition.
      transitions_[t].src = null_state();
      transitions_fs_.emplace_back(t);
    }

    void
    del_transition(state_t src, state_t dst, label_t l)
    {
      transition_t t = get_transition(src, dst, l);
      if (t != null_transition())
        del_transition(t);
    }

    transition_t
    new_transition(state_t src, state_t dst, label_t l, weight_t w)
    {
      assert(!has_transition(src, dst, l));
      if (weightset()->is_zero(w))
        return null_transition();
      else
        {
          // FIXME: When src == pre() || dst == post(), label must be empty.
          transition_t t;
          if (transitions_fs_.empty())
            {
              t = transitions_.size();
              transitions_.emplace_back(src, dst, l, w);
            }
          else
            {
              t = transitions_fs_.back();
              transitions_fs_.pop_back();
              stored_transition_t& st = transitions_[t];
              st.src = src;
              st.dst = dst;
              st.set_label(l);
              st.set_weight(w);
            }
          states_[src].succ.emplace_back(t);
          states_[dst].pred.emplace_back(t);
          return t;
        }
    }

    template <Automaton A>
    transition_t
    new_transition_copy(state_t src, state_t dst,
                        const A& aut, transition_t_of<A> t,
                        bool transpose = false)
    {
      auto l = aut->label_of(t);
      auto w = aut->weight_of(t);
      if (transpose)
        {
          l = aut->labelset()->transpose(l);
          w = aut->weightset()->transpose(w);
        }
      return new_transition(src, dst,
                            labelset()->conv(*aut->labelset(), l),
                            weightset()->conv(*aut->weightset(), w));
    }

    transition_t
    new_transition(state_t src, state_t dst, label_t l)
    {
      return new_transition(src, dst, l, weightset()->one());
    }

    transition_t
    set_transition(state_t src, state_t dst, label_t l, weight_t w)
    {
      // It's illegal to connect pre() to post().
      // FIXME: reenable except for labels_are_one.
      // assert(src != pre() || dst != post());
      // It's illegal to leave post().
      assert(src != post());
      // It's illegal to go to pre().
      assert(dst != pre());

      transition_t t = get_transition(src, dst, l);
      if (t == null_transition())
        t = new_transition(src, dst, l, w);
      else if (weightset()->is_zero(w))
        {
          del_transition(t);
          t = null_transition();
        }
      else
        {
          stored_transition_t& st = transitions_[t];
          st.set_label(l);
          st.set_weight(w);
        }
      return t;
    }

    transition_t
    set_transition(state_t src, state_t dst, label_t l)
    {
      return set_transition(src, dst, l, weightset()->one());
    }

    transition_t
    add_transition(state_t src, state_t dst, label_t l, weight_t w)
    {
      transition_t t = get_transition(src, dst, l);
      if (t == null_transition())
        t = new_transition(src, dst, l, w);
      else
        {
          w = weightset()->add(weight_of(t), w);
          t = set_weight(t, w);
        }
      return t;
    }

    transition_t
    add_transition(state_t src, state_t dst, label_t l)
    {
      return add_transition(src, dst, l, weightset()->one());
    }

    template <Automaton A>
    transition_t
    add_transition_copy(state_t src, state_t dst,
                        const A& aut, transition_t_of<A> t,
                        bool transpose = false)
    {
      auto l = aut->label_of(t);
      auto w = aut->weight_of(t);
      if (transpose)
        {
          l = aut->labelset()->transpose(l);
          w = aut->weightset()->transpose(w);
        }
      return add_transition(src, dst,
                            labelset()->conv(*aut->labelset(), l),
                            weightset()->conv(*aut->weightset(), w));
    }

    std::ostream& print(transition_t t, std::ostream& o = std::cout,
                        format fmt = {}) const
    {
      if (t == null_transition())
        o << "null_transition";
      else if (t == lazy_transition())
        o << "lazy_transition";
      else
        {
          o << t << ": ";
          print_state_name(src_of(t), o) << " -- <";
          weightset()->print(weight_of(t), o, fmt.for_weights()) << '>';
          labelset()->print(label_of(t), o, fmt.for_labels()) << " --> ";
          print_state_name(dst_of(t), o);
        }
      return o;
    }

    std::ostream& print(std::ostream& o = std::cout) const
    {
      for (auto s: all_states())
        {
          o << "State: ";
          print_state_name(s, o) << '\n';
          o << "  Incoming:\n";
          for (auto t: all_in(s))
            {
              o << "    ";
              print(t, o) << '\n';
            }
          o << "  Outgoing:\n";
          for (auto t: all_out(s))
            {
              o << "    ";
              print(t, o) << '\n';
            }
        }
      return o;
    }

    transition_t
    set_weight(transition_t t, weight_t w)
    {
      if (weightset()->is_zero(w))
        {
          del_transition(t);
          return null_transition();
        }
      else
        transitions_[t].set_weight(w);
      return t;
    }

    weight_t
    add_weight(transition_t t, weight_t w)
    {
      return weight_of(set_weight(t, weightset()->add(weight_of(t), w)));
    }

    weight_t
    lweight(transition_t t, weight_t w)
    {
      return weight_of(set_weight(t, weightset()->mul(w, weight_of(t))));
    }

    weight_t
    rweight(transition_t t, weight_t w)
    {
      return weight_of(set_weight(t, weightset()->mul(weight_of(t), w)));
    }


    /*---------------------------------------.
    | Iteration on states and transitions.   |
    `---------------------------------------*/

  protected:
    template <typename Pred>
    auto state_range(state_t b, state_t e, Pred pred) const
    {
      return make_container_filter_range
        (boost::irange<state_t>(b, e),
         [this, pred]
         (state_t s)
         {
           const stored_state_t& ss = states_[s];
           return ((ss.succ.empty()
                    || ss.succ.front() != null_transition())
                   && pred(s));
         });
    }

    auto state_range(state_t b, state_t e) const
    {
      return state_range(b, e, [](state_t) { return true; });
    }

  public:
    auto all_states() const
    {
      return state_range(0U, states_.size());
    }

    template <typename Pred>
    auto all_states(Pred pred) const
    {
      return state_range(0U, states_.size(), pred);
    }

    auto states() const
    {
      return state_range(post() + 1, states_.size());
    }

    auto all_transitions() const
    {
      return make_container_filter_range
        (boost::irange<transition_t>(0U, transitions_.size()),
         [this](transition_t t)
         {
           return src_of(t) != null_state();
         });
    }

    container_range<const tr_cont_t&>
    all_out(state_t s) const
    {
      assert(has_state(s));
      return states_[s].succ;
    }

    container_range<const tr_cont_t&>
    all_in(state_t s) const
    {
      assert(has_state(s));
      return states_[s].pred;
    }
  };
  }

  template <typename Context>
  mutable_automaton<Context>
  make_mutable_automaton(const Context& ctx)
  {
    return make_shared_ptr<mutable_automaton<Context>>(ctx);
  }

  template <typename Context>
  auto
  make_nullable_automaton(const Context& ctx)
  {
    return make_mutable_automaton(make_nullableset_context(ctx));
  }
}