dfa_matrix.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_matrix
//   Representation by a matrix Q x Sigma

#ifndef ASTL_DFA_MATRIX_H
#define ASTL_DFA_MATRIX_H

#include <iterator>   // iterator_tag
#include <functional> // less<>
#include <utility>    // pair<>
#include <vector>

#include <dfa_base.h>

ASTL_BEGIN_NAMESPACE

#include <iostream>

// g++ 3.2.2 bug workaround
// g++ 3.2.2 sees matrix_line as a variably modified type
#if (__GNUG__ == 3) && (__GNUC_MINOR__ == 2) && (__GNUC_PATCHLEVEL__ == 2)
#define MATRIX_PATCH
#endif

template <typename Sigma>
class matrix_line
{
public:
  unsigned int size_;//    a count of the outgoing transitions
#ifdef MATRIX_PATCH
  unsigned int *v;
#else
  unsigned int v[Sigma::size];
#endif

  typedef matrix_line self;

  matrix_line() : size_(0) {
#ifdef MATRIX_PATCH
    v = new unsigned int[Sigma::size];
#endif
    memset(v, 0, Sigma::size * sizeof(unsigned int));

  }

#ifdef MATRIX_PATCH
  ~matrix_line() {
    delete [] v;
  }
#endif

  matrix_line(const self &x)
    : size_(x.size_) {
#ifdef MATRIX_PATCH
    v = new unsigned int[Sigma::size];
#endif
    memcpy(v, x.v, Sigma::size * sizeof(unsigned int));
  }

  self& operator=(const self &x) {
    size_ = x.size_;
    memcpy(v, x.v, Sigma::size * sizeof(unsigned int));
    return (*this);
  }

  bool operator==(const self &x) const {
    return size_ == x.size_ && equal(v, v + Sigma::size, x.v);
  }

  size_t size() const {
    return size_;
  }
  
  size_t& size() {
    return size_;
  }
};

template <class Sigma_ = plain,
          class Tag_   = empty_tag>
class DFA_matrix : public DFA_base<Sigma_, Tag_, matrix_line<Sigma_> >
{
public:
  typedef DFA_base<Sigma_, Tag_, matrix_line<Sigma_> > super;
  typedef typename super::char_traits     char_traits;
  typedef Tag_                            tag_type;
  typedef typename char_traits::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
  {
  protected:
    typedef matrix_line<char_traits> Container;
    const Container *container;

  public:
    typedef char_type                         key_type;
    typedef state_type                        data_type;
    typedef pair<const char_type, state_type> value_type;

    struct key_compare : public binary_function<key_type, key_type, bool>
    {
      bool operator()(const key_type &x, const key_type &y) const {
	return char_traits::to_int_type(x) < char_traits::to_int_type(y);
      }
    };

    struct value_compare : public binary_function<value_type, value_type, bool>
    {
      bool operator()(const value_type &x, const value_type &y) const {
	return char_traits::to_int_type(x.first) < char_traits::to_int_type(y.first);
      }
    };
    typedef const value_type& const_reference;
    typedef int               difference_type;

#ifndef __MSC_VER
    typedef typename char_traits::int_type    size_type;
#else
    typedef unsigned long size_type;
#endif

#if (__GNUG__ && __GNUG__ < 3)
    class const_iterator : public bidirectional_iterator<value_type, ptrdiff_t>
#else
    class const_iterator : public iterator<bidirectional_iterator_tag, value_type>
#endif
    {
      friend class edges_type;
      typedef const_iterator self;

    protected:
      const state_type *i;
      const Container *c;

      const_iterator(const state_type *_i, const Container *_c)
	: i(_i), c(_c) 
      { }

    public:
      const_iterator()
      { }

      bool operator== (const self& x) const {
	return (x.i == i); 
      }

      bool operator!= (const self& x) const {
	return !(*this == x);
      }

      typename const_iterator::value_type operator* () const { 
	return (make_pair(char_traits::to_char_type(i - c->v), *i)); 
      }

      self& operator ++ ()       
      { 
	for(++i; i != (c->v + char_traits::size) && *i == 0; ++i);
	return (*this);
      }

      self operator ++ (int) 
      { 
	const_iterator tmp = *this;
	++(*this);
	return (tmp);
      }

      self& operator -- () 
      { 
	for(--i; *i == 0; --i);
	return (*this);
      }

      self operator -- (int) 
      { 
	const_iterator tmp = *this;
	--(*this);
	return (tmp);
      }
    };

#ifdef _MSC_VER
    typedef reverse_iterator<const_iterator, const_iterator::value_type> const_reverse_iterator;
#else
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
#endif

    // allocation/deallocation:
    edges_type(const Container *c = NULL)
      : container(c) { }
    
    const_iterator begin() const { 
      const_iterator result(container->v, container);
      if (*(result.i) == 0)
	++result;
      return (result); 
    }
    
    const_iterator end() const {
      const_iterator result(container->v + char_traits::size, container);
      return (result);
    }

    const_reverse_iterator rbegin() const { 
      return (const_reverse_iterator(end())); 
    }
    
    const_reverse_iterator rend() const {
      return (const_reverse_iterator(begin())); 
    }
    
    bool empty() const { 
      return size() == 0;
    }
    
    size_type size() const { 
      return container->size(); 
    }

    size_type max_size() const { 
      return char_traits::size; 
    }
    
    // map operations:
    key_compare key_comp() const {
      return key_compare();
    }

    value_compare value_comp() const {
      return value_compare();
    }

    const_iterator find(const key_type& x) const { 
      if (container->v[char_traits::to_int_type(x)] == 0) 
	return end();
      else
      return const_iterator(container->v + char_traits::to_int_type(x), container);
    }
    
    size_type count(const key_type& x) const { 
      return (container->v[char_traits::to_int_type(x)] == 0) ? 0 : 1;
    }
    
    // comparison:
    friend bool operator==(const edges_type& x, const edges_type& y) {
      return (x.container == y.container || *x.container == *y.container);
    }

    const_iterator lower_bound(const key_type &k) const {
      return find(k);
    }

    const_iterator upper_bound(const key_type &k) const {
      const_iterator i = find(k);
      return i == end() ? i : ++i;
    }

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

  // Backward compatibility
  typedef edges_type Edges;

  void del_trans(state_type s, const char_type &l)
  {
    Q[s]->edges().v[char_traits::to_int_type(l)] = 0;
    --Q[s]->edges().size();
    --trans_count_;
  }

  void change_trans(state_type s, const char_type &l, state_type new_aim) {
    Q[s]->edges().v[char_traits::to_int_type(l)] = new_aim;
  }

  state_type delta1(state_type s, const char_type &l) const {
    return Q[s]->edges().v[char_traits::to_int_type(l)];
  }

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

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

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

ASTL_END_NAMESPACE

#endif  // ASTL_DFA_MATRIX_H