dfa_hash.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
 *
 */

#ifndef ASTL_DFA_HASH_H
#define ASTL_DFA_HASH_H

// Descrition:	
//   ASTL 2.0 Determinisic Finite Automaton Class Template DFA_hash
//   Representation by a unique hash table
//   This class implements a restricted subset of the DFA requirements
//   (no tags, no edges traversal, no state/transition deletions)                 

#if defined(__GNUG__)
#if (__GNUG__ < 3)
#include <hash_map>
#else
#include <ext/hash_map>
#endif
#endif
#include <utility>  // pair<>
#include <functional>
#include <astl.h>
#include <concept.h>

ASTL_BEGIN_NAMESPACE

template <class Sigma_ = plain>
class DFA_hash : public DFA_concept
{
public:
  typedef Sigma_ char_traits;
  typedef typename char_traits::char_type char_type;
  typedef empty_tag tag_type;
  typedef size_t state_type;

  // Backward compatibility
  typedef char_traits Sigma;
  typedef char_type   Alphabet;
  typedef state_type  State;
  typedef tag_type    Tag;

protected:
  typedef pair<state_type, char_type> key;
  typedef state_type                 data;
  struct hash_function : public unary_function<pair<state_type, char_type>, size_t>
  {
    size_t operator() (const pair<state_type, char_type> &x) const {
      return x.first * 1023 + char_traits::to_int_type(x.second);
    }
  };

#if defined(__GNUG__)
#if (__GNUG__ < 3)
  typedef hash_map<key, data, hash_function, equal_to<key> > hasher_type;
#else	
  typedef __gnu_cxx::hash_map<key, data, hash_function, equal_to<key> > hasher_type;
#endif
#else
  typedef map<key, data, less<key> > hasher_type;
#endif
  hasher_type hasher;

  unsigned long state_count_;
  state_type    current;
  state_type    I;
  vector<char>  F;
  Tag           bogus;

public:
#ifndef _MSC_VER
  static const state_type null_state = 0;
#else
  static const state_type null_state;
#endif

  /*
    class edges_type 
    {
    protected:
    state_type  q;
    const hasher_type *h;

    public:
    edges_type()
    : q(0), h(NULL)
    { }

    edges_type(state_type p, const hasher_type &H)
    : q(p), h(&H)
    { }

    typedef size_t                      size_type;
    typedef char_type                    key_type;
    typedef state_type                       data_type;
    typedef pair<const char_type, state_type> value_type;

    class const_iterator : public bidirectional_iterator<edges_type::value_type, ptrdiff_t>
    {
    protected:
    state_type q;
    typename char_traits::const_iterator i;
    const hasher_type *h;

    public:
    typedef const_iterator self;

    const_iterator()
    { }

    const_iterator(state_type p, typename char_traits::const_iterator j, const hasher_type &H)
    : q(p), i(j), h(&H)
    { }

    edges_type::value_type operator* () const {
    return make_pair(*i, (*(h->find(make_pair(q, *i)))).second);
    }
			
    self& operator++ () {
    for(++i; i != char_traits::end() && h->find(make_pair(q, *i)) == h->end(); ++i);
    return *this;
    }
			
    self operator++ (int) {
    self tmp = *this;
    ++*this;
    return tmp;
    }
			
    bool operator== (const self &x) const {
    return i == x.i;
    }
    };

    const_iterator begin() const {    // linear time !!!
    const_iterator r(q, char_traits::begin(), *h);
    if (h->find(make_pair(q, *(char_traits::begin()))) == h->end())
    ++r;
    return r;
    }

    const_iterator end() const {
    return const_iterator(q, char_traits::end(), *h);
    }

    size_t size() const {     // linear time !!!
    size_t r = 0;
    distance(begin(), end(), r);
    return r;
    }

    bool empty() const {      // linear time !!!
    return begin() == end();
    }

    bool operator==(const edges_type &x) const {
    return lexicographical_compare_3way(begin(), end(), x.begin(), x.end()) == 0;
    }

    const_iterator find(const key_type &k) const {
    hasher_type::const_iterator i = h->find(make_pair(q, k));
    if (i == h->end()) return end();
    return const_iterator(q, k, *h);
    }

    size_t count(const key_type &k) const {
    return find(k) == end() ? 0 : 1;
    }

    pair<const_iterator, const_iterator> equal_range(const key_type &k) const {
    const_iterator r = find(k);
    if (r == end()) return make_pair(r, r);
    return make_pair(r, ++r);
    }
    };   

    // Backward compatibility
    typedef edges_type Edges;
  */

  DFA_hash(unsigned long = 0)
    : state_count_(0), current(0), 
      I(0), F(1, '\0')
  { }

  state_type new_state() {
    ++state_count_;
    F.push_back('\0');
    return ++current;
  }

  template <class OutputIterator>
  OutputIterator new_state(unsigned long how_many, OutputIterator x) {
    for(; how_many > 0; --how_many)
      *x++ = new_state();
    return x;
  }

  bool final(state_type s) const {
    return F[s] != '\0';
  }

  char& final(state_type s) {
    return F[s];
  }

  /*
    void del_state(state_type s) {   // linear !!!!
    if (s == initial()) initial(null_state);
    pair<state_type, char_type> p(s, char_type());
    for(typename _char_traits::const_iterator i = _char_traits::begin(); i != _char_traits::end(); ++i) {
    p.second = *i;
    hasher.erase(p);
    }
    --state_count_;
    }

    void copy_state(state_type from, state_type to) {   // linear !!!!
    del_state(to);
    ++state_count_;  // because del_state decrements state_count
    pair<state_type, char_type> pfrom(from, char_type()), pto(to, char_type());
    for(typename _char_traits::const_iterator i = _char_traits::begin(); i != _char_traits::end(); ++i) {
    pfrom.second = *i;
    hasher_type::const_iterator j = hasher.find(pfrom);
    if (j != hasher.end()) {
    pto.second = *i;
    hasher[pto] = (*j).second;
    }
    }
    final(to) = final(from);
    }
		
    state_type duplicate_state(state_type q) {     // linear !!!!!
    state_type p = new_state();
    pair<state_type, char_type> pfrom(q, char_type()), pto(p, char_type());
    for(typename _char_traits::const_iterator i = _char_traits::begin(); i != _char_traits::end(); ++i) {
    pfrom.second = *i;
    hasher_type::const_iterator j = hasher.find(pfrom);
    if (j != hasher.end()) {
    pto.second = *i;
    hasher[pto] = (*j).second;
    }
    }
    final(p) = final(q);
    return q;
    }
  */

  state_type initial() const { 
    return (I); 
  }

  void initial(state_type s) { 
    I = s; 
  }

  void set_trans(state_type s, const char_type &a, state_type aim) {
    hasher[make_pair(s, a)] = aim;
  }

  void del_trans(state_type s, const char_type &a) {
    hasher.erase(make_pair(s, a));
  }

  void change_trans(state_type s, const char_type &a, state_type new_aim) {
    hasher[make_pair(s, a)] = new_aim;
  }

  state_type delta1(state_type s, const char_type &a) const {
    typename hasher_type::const_iterator i = hasher.find(make_pair(s, a));
    return i == hasher.end() ? null_state : (*i).second;
  }

  /*
    edges_type delta2(state_type s) const {
    return edges_type(s, hasher);
    }
  */
  unsigned long state_count() const { 
    return (state_count_); 
  } 

  unsigned long trans_count() const { 
    return hasher.size();
  }

  Tag& tag(state_type) {
    return bogus;
  }
	
  const Tag& tag(state_type) const {
    return bogus;
  }
};

#ifndef _MSC_VER
template <class T>
const typename DFA_hash<T>::state_type DFA_hash<T>::null_state;
#else
template <class T>
const DFA_hash<T>::state_type DFA_hash<T>::null_state = 0;
#endif

ASTL_END_NAMESPACE

#endif // ASTL_CLASS_DFA_HASH