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@gamned.org
*/
#ifndef __CLAW_AUTOMATON_HPP__
#define __CLAW_AUTOMATON_HPP__

#include <map>
#include <vector>
#include <claw/avl.hpp>

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

} // namespace claw

#include <claw/impl/automaton.tpp>

#endif // __CLAW_AUTOMATON_HPP__