dfa_map.h

一个类似STL的自动机的源代码库

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2003 Vincent Le Maout ([e-mail]).
 * 
 * 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

// Descrition:	
//   ASTL 2.0 Determinisic Finite Automaton Class Template DFA_map
//   Representation by STL map

#ifndef ASTL_DFA_MAP_H
#define ASTL_DFA_MAP_H

#include <map>            
#include <vector>  
#include <functional>   // binary_function<>       
#include <astl.h>
#include <dfa_base.h>

ASTL_BEGIN_NAMESPACE

template <typename CharTraits>
struct dfa_map_key_compare 
  : public binary_function<typename CharTraits::char_type, typename CharTraits::char_type, bool>
{
  bool operator()(const typename CharTraits::char_type &x, 
		  const typename CharTraits::char_type &y) const {
    return CharTraits::lt(x, y);
  }
};

template <class Sigma_ = plain,
          class Tag_   = empty_tag>
class DFA_map 
  : public DFA_base<Sigma_, Tag_, map<typename Sigma_::char_type, 
				      unsigned int, dfa_map_key_compare<Sigma_> > > 
{
protected:
  typedef map<typename Sigma_::char_type, unsigned int, 
	      dfa_map_key_compare<Sigma_> > transition_container;

public:
  typedef DFA_base<Sigma_, Tag_, transition_container> super;
  typedef Sigma_                          char_traits;
  typedef Tag_                            tag_type;
  typedef typename Sigma_::char_type      char_type;
  typedef unsigned int                    state_type;
  
  // Backward compatibility
  typedef char_traits Sigma;
  typedef char_type   Alphabet;
  typedef tag_type    Tag;
  typedef state_type  State;

  class edges_type
  {
    friend class DFA_map;
  private:
    const transition_container *container;
    
  public:
    typedef typename transition_container::key_type        key_type;
#ifndef _MSC_VER
    typedef typename transition_container::data_type       data_type;
#endif
    typedef typename transition_container::value_type      value_type;
    typedef typename transition_container::key_compare     key_compare;
    typedef typename transition_container::const_reference const_reference;
    typedef typename transition_container::size_type       size_type;
    typedef typename transition_container::difference_type difference_type;
    typedef typename transition_container::value_compare   value_compare;

    typedef typename transition_container::const_iterator         const_iterator;
    typedef typename transition_container::const_reverse_iterator const_reverse_iterator;

    // allocation/deallocation:
    
  protected:
    edges_type(const transition_container *c)
      : container(c) { }

  public:
    edges_type(const edges_type& x) : container(x.container) { }
    ~edges_type() { }
    
    // accessors:
    key_compare key_comp() const { return (container->key_comp()); } 
    value_compare value_comp() const { return (container->value_comp()); }
    const_iterator begin() const { return (container->begin()); }
    const_iterator end() const { return (container->end()); }
    const_reverse_iterator rbegin() const { return (container->rbegin()); }
    const_reverse_iterator rend() const { return (container->rend()); }
    bool empty() const { return (container->empty()); }
    size_type size() const { return (container->size()); }
    size_type max_size() const { return (container->max_size()); }
    
    // map operations:
    const_iterator find(const key_type& x) const { return (container->find(x)); }
    size_type count(const key_type& x) const { return (container->count(x)); }
    const_iterator lower_bound(const key_type& x) const { return (container->lower_bound(x)); }
    const_iterator upper_bound(const key_type& x) const { return (container->upper_bound(x)); }
    pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
      return (container->equal_range(x));
    }

    // comparison:
    friend bool operator == (const edges_type& x, const edges_type& y) {
      return (x.container == y.container || *x.container == *y.container);
    }
  };

  typedef unsigned int                state_type;
  
  // Backward compatibility
  typedef edges_type Edges;
  
  void del_trans(state_type s, const char_type &l)
  {
    Q[s]->edges().erase(l);
    --trans_count_;
  }

  void change_trans(state_type s, const char_type &l, state_type aim) {
    Q[s]->edges()[l] = aim;
  }

  state_type delta1(state_type s, const char_type &l) const
  {
    typename transition_container::iterator vi = Q[s]->edges().find(l);
    return vi == Q[s]->edges().end() ? null_state : (*vi).second;
  }

  void set_trans(state_type s, const char_type &l, state_type aim)
  {
    Q[s]->edges()[l] = aim;
    ++trans_count_;
  }

  edges_type delta2(state_type s) const { 
    return edges_type(&Q[s]->edges()); 
  }

  DFA_map(unsigned long n = 0) 
    : super(n)
  { }
};

ASTL_END_NAMESPACE

#endif   // ASTL_DFA_MAP_H