automaton.hpp

Go to the documentation of this file.

/*
  CLAW - a C++ Library Absolutely Wonderful
 
  CLAW is a free library without any particular aim but being useful to
  anyone.
 
  Copyright (C) 2005-2011 Julien Jorge
 
  This library 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 2.1 of the License, or (at your option) any later version.
 
  This library 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 this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
  contact: julien.jorge@stuff-o-matic.com
*/
#ifndef __CLAW_AUTOMATON_HPP__
#define __CLAW_AUTOMATON_HPP__
 
#include <claw/avl.hpp>
#include <map>
#include <vector>
 
namespace claw
{
  //***************************** automate ************************************

  template <class State, class Edge, class StateComp = std::less<State>,
            class EdgeComp = std::less<Edge> >
  class automaton
  {
  public:
    typedef State state_type;

    typedef Edge edge_type;

    typedef StateComp state_compare;

    typedef EdgeComp edge_compare;

    typedef std::multimap<edge_type, state_type, edge_compare> neighbours_list;

    typedef std::map<state_type, neighbours_list, state_compare> adjacent_list;

    typedef std::vector<state_type> result_state_list;

    typedef std::vector<edge_type> result_edge_list;
 
  public:
    void add_edge(const state_type& s1, const state_type& s2,
                  const edge_type& e);
    void remove_edge(const state_type& s1, const state_type& s2,
                     const edge_type& e);
 
    void add_state(const state_type& s);
    void add_initial_state(const state_type& s);
    void add_final_state(const state_type& s);
 
    bool state_exists(const state_type& s) const;
    bool state_is_final(const state_type& s) const;
    bool state_is_initial(const state_type& s) const;
 
    void states(result_state_list& v) const;
    void final_states(result_state_list& v) const;
    void initial_states(result_state_list& v) const;
    void alphabet(result_edge_list& v) const;
 
    template <class InputIterator>
    bool match(InputIterator first, InputIterator last) const;
 
    unsigned int states_count() const;
 
    void reachables(const state_type& s, const edge_type& e,
                    result_state_list& l) const;
    void reachables(const state_type& s, result_state_list& l) const;
 
    void edges(const state_type& s1, const state_type& s2,
               result_edge_list& l) const;
    void edges(const state_type& s1, const edge_type& edge,
               result_edge_list& l) const;
 
  private:
    template <class InputIterator>
    bool match_aux(const state_type& s, InputIterator first,
                   InputIterator last) const;
 
  private:
    static state_compare s_state_compare;

    avl<edge_type, edge_compare> m_alphabet;

    avl<state_type, state_compare> m_initial_states;

    avl<state_type, state_compare> m_final_states;

    adjacent_list m_states;
  }; // automaton
 
}
 
#include <claw/automaton.tpp>
 
#endif // __CLAW_AUTOMATON_HPP__