automaton.h

/*
 * Copyright 2016, IST Austria
 *
 * This file is part of Limi.
 *
 * Limi is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Limi is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Limi.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef LIMI_AUTOMATON_H
#define LIMI_AUTOMATON_H

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <ostream> 
#include <algorithm>
#include <deque>
#include <iostream>
#include "generics.h"
#include "internal/hash.h"

namespace Limi {


template <class State, class Symbol, class Implementation>
class automaton
{
public:
  using Symbol_ = Symbol;
  using State_ = State;
  automaton(bool collapse_epsilon = false, bool no_epsilon_produced = false) : collapse_epsilon(collapse_epsilon && !no_epsilon_produced), no_epsilon_produced(no_epsilon_produced)  {}
  
  ~automaton() {
    delete state_printer_;
    delete symbol_printer_;
  }
  
  using State_set = std::unordered_set<State>;
  using Symbol_set = std::unordered_set<Symbol>;
  using State_vector = std::vector<State>;
  using Symbol_vector = std::vector<Symbol>;
  
  /***********************************************
   * Internal functions that need to be overriden by the deriving class
   **********************************************/
  
  inline printer_base<State>* int_state_printer() const { return new printer<State>(); }
  
  inline printer_base<Symbol>* int_symbol_printer() const { return new printer<Symbol>(); }
  
  bool int_is_final_state(const State& state) const;
  
  void int_initial_states(State_vector& states) const;
  
  void int_successors(const State& state, const Symbol& sigma, State_vector& successors) const;
  
  void int_next_symbols(const State& state, Symbol_vector& symbols) const;
  
  bool int_is_epsilon(const Symbol& symbol) const;
  
  /***********************************************
   * Public functions
   **********************************************/

  inline bool is_final_state(const State& state) const { return impl().int_is_final_state(state); }
  
  inline void initial_states(State_vector& states) const { 
    impl().int_initial_states(states);
    explore_epsilon(states);
  }
  
  inline void initial_states(State_set& states) const { 
    State_vector initial;
    initial_states(initial);
    states.insert(initial.begin(), initial.end());
  }
  
  inline State_vector initial_states() const { 
    State_vector result;
    initial_states(result);
    return result;
  }
  
  void successors(const State& state, const Symbol& sigma, State_vector& successors1) const {
    impl().int_successors(state, sigma, successors1);
    explore_epsilon(successors1); 
  }
  
  inline State_set successors(const State_set& states, const Symbol& sigma) const
  {
    State_set result;
    successors(states, sigma, result);
    return result;
  }
  
  inline void successors(const State_set& states, const Symbol& sigma, State_set& successors1) const
  {
    State_vector successors2;
    for (const State& state : states) {
      successors(state, sigma, successors2);
    }
    successors1.insert(successors2.begin(), successors2.end());
  }
  
  
  inline State_vector successors(const State& state, const Symbol& sigma) const { 
    State_vector result;
    successors(state, sigma, result);
    return result;
  }
  
  inline void next_symbols(const State& state, Symbol_vector& symbols) const { 
    impl().int_next_symbols(state, symbols); 
    filter_epsilon(symbols);
  }
  
  inline Symbol_vector next_symbols(const State& state) const {
    Symbol_vector result;
    next_symbols(state, result);
    return result;
  }
  
  inline void next_symbols(const State& state, Symbol_set& symbols) const {
    Symbol_vector result;
    next_symbols(state, result);
    symbols.insert(result.begin(), result.end());
  }
  
  inline const printer_base<State>& state_printer() const { 
    if (!state_printer_) state_printer_ = impl().int_state_printer();
    return *state_printer_;
  }
  
  inline const printer_base<Symbol>& symbol_printer() const { 
    if (!symbol_printer_) symbol_printer_ = impl().int_symbol_printer();
    return *symbol_printer_; 
    
  }
  
  inline bool is_epsilon(const Symbol& symbol) const { return impl().int_is_epsilon(symbol); }
  
  inline bool is_final_state(const State_set& states) const {
    for (State s:states) {
      if (is_final_state(s)) 
        return true;
    }
    return false;
  }
  
  

  
  bool collapse_epsilon;
  
  bool no_epsilon_produced;
private:
  mutable const printer_base<State>* state_printer_ = nullptr;
  mutable const printer_base<Symbol>* symbol_printer_ = nullptr;
  
  inline Implementation& impl() {
    return *static_cast<Implementation*>(this);
  }
  inline const Implementation& impl() const {
    return *static_cast<const Implementation*>(this);
  }
  
  void filter_epsilon(Symbol_vector& symbols) const {
    if (collapse_epsilon) {
      for (auto it = symbols.begin(); it!=symbols.end(); ) {
        if (impl().int_is_epsilon(*it))
          it = symbols.erase(it);
        else
          ++it;
      }
    }
  }
  
  void explore_epsilon(State_vector& states) const {
    if (!collapse_epsilon) return;
    State_set seen;
    std::deque<State> frontier;
    frontier.insert(frontier.begin(), states.begin(), states.end());
    states.clear();
    while(!frontier.empty()) {
      const State& s = frontier.front();
      //state_printer()(s, std::cout); std::cout << std::endl;

      Symbol_vector next_symbols;
      impl().int_next_symbols(s, next_symbols);
      State_vector succs;
      bool first = true;
      if (impl().int_is_final_state(s)) {
        first = false;
        states.push_back(s);
      }
      for (const Symbol& sy : next_symbols) {
        if (impl().int_is_epsilon(sy)) {
          impl().int_successors(s, sy, succs);
        } else if (first) { // if there is at least one non-epsilon transition we add this state
          first = false;
          states.push_back(s);
        }
      }
      for (const State& st : succs) {
        if (seen.insert(st).second) {
          frontier.push_back(st);
        }
      }
      frontier.pop_front();
    }
    //std::cout << std::endl;
  }
};
}

#endif // LIMI_AUTOMATON_H