dfa_base.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_BASE_H
#define ASTL_DFA_BASE_H

// DFA_matrix, DFA_bin, DFA_mtf, DFA_tr, DFA_map derive from this base class
// This class manages state structures allocation/deallocation

#include <vector>
#include <concept.h>
#include <state.h>

using std::vector;

ASTL_BEGIN_NAMESPACE

template <class CharTraits, class TagType, class StateData_>
class DFA_base : public DFA_concept
{
public:
  typedef CharTraits                     char_traits;
  typedef TagType                        tag_type;
  typedef typename CharTraits::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;

protected:
  typedef vector<char> set_F;
  typedef state_data<tag_type, StateData_> StateData;

  vector<StateData*> Q;
  state_type         I;
  set_F              F;
  unsigned long      state_count_;
  unsigned long      trans_count_;

public:
  typedef skip_blanks_iterator<StateData> const_iterator;

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

  const_iterator begin() const {
    const_iterator x(&Q, 0);
    return ++x;
  }

  const_iterator  end() const { 
    return const_iterator(&Q, Q.size()); 
  }

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

  state_type initial() const { 
    return I; 
  }

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

  state_type new_state() {
    Q.push_back(new StateData);
    F.push_back('\0');
    ++state_count_;
    return Q.size() - 1;
  }

  template <class OutputIterator>
  OutputIterator new_state(unsigned long how_many, OutputIterator x)
  {
    for(; how_many > 0; --how_many)
      *x++ = new_state();
    return x;
  }
      
  void del_state(state_type s) 
  {
    if (s == initial()) initial(null_state);
    trans_count_ -= Q[s]->edges().size();
    delete Q[s];
    Q[s] = NULL;
    --state_count_;
  }

  void copy_state(state_type from, state_type to) {
    trans_count_ += Q[from]->edges().size() - Q[to]->edges().size();
    *Q[to] = *Q[from];
    F[to] = F[from];
  }

  state_type duplicate_state(state_type q)
  {
    Q.push_back(new StateData(*Q[q]));
    F.push_back(F[q]);
    ++state_count_;
    trans_count_ += Q[q]->edges().size();
    return Q.size() - 1;
  }

  unsigned long state_count() const { 
    return state_count_; 
  }
  
  unsigned long trans_count() const { 
    return trans_count_; 
  }
  
  tag_type& tag(state_type s) { 
    return Q[s]->tag(); 
  }
  
  const tag_type& tag(state_type s) const { 
    return Q[s]->tag(); 
  }

  DFA_base(unsigned long n) :
    Q(1, (StateData*) 0), I(0), F(1, '\0'), state_count_(0UL), 
    trans_count_(0UL) { 
    Q.reserve(n + 1);
  }

  ~DFA_base()
  {
    const_iterator start, finish = end();
    for(start = begin(); start != finish; ++start)
      del_state(*start);
  }
};

#ifndef _MSC_VER
template <class CharTraits, class TagType, class StateData_>
const typename DFA_base<CharTraits, TagType, StateData_>::state_type 
DFA_base<CharTraits, TagType, StateData_>::null_state;
#else
template <class CharTraits, class TagType, class StateData_>
const typename DFA_base<CharTraits, TagType, StateData_>::state_type 
DFA_base<CharTraits, TagType, StateData_>::null_state = 0;
#endif

ASTL_END_NAMESPACE

#endif  // CLASS_DFA_MATRIX