default.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_DEFAULT_H
#define ASTL_DEFAULT_H

#include <astl.h>

ASTL_BEGIN_NAMESPACE

// Defines:
// 1. template def_trans_cursor (cursor adapter)
// 2. template default_state_cursor      (forward cursor adapter)
// 3. template substitute_state_cursor   (forward cursor adapter)

//
// A def_trans_cursor (default transition cursor) uses the transition labelled 
// with default_letter when the required transition is undefined.
//
// Instanciation parameters:
// 1. Cursor: the cursor type to be adapted which is a model of the plain cursor concept.
//
// Requirements:
// None
//
// Remark: the default transition does not appear in the outgoing transition traversal
//         TODO: what should be done for the method find ?
//
template <typename Cursor>
class def_trans_cursor : public Cursor
{
protected:
  int def_letter;

public:
  typedef Cursor           super;
  typedef def_trans_cursor self;
  
  def_trans_cursor(const ForwardCursor &x, int default_letter = 0)
    : super(x), def_letter(default_letter)
  { }

  bool forward(int letter) {
    if (super::find(letter)) {
      forward();
      return true;
    }
    return super::forward(def_letter);
  }

  self& operator= (State p) {
    super::operator=(p);
    return *this;
  }
};

// A def_state_cursor (default state cursor) moves to default state when required 
// transition is undefined (makes the DFA complete and make the default state the
// new sink state).
//
// Instanciation parameters:
// 1. ForwardCursor: the cursor type to be adapted which is a model of the forward cursor concept. 
//
// Requirements:
// the default state is an existing state
//
// Warning: this makes the automaton cyclic
//
// TODO:
// What should be done for find and outgoing transitions traversal

template <class ForwardCursor>
class def_state_cursor : public ForwardCursor
{
public:
  typedef typename ForwardCursor::State State;
  typedef ForwardCursor        super;
  typedef def_state_cursor self;
  
protected:
  State def_state;

public:
  def_state_cursor(const ForwardCursor &x, const State &default_state)
    : super(x), def_state(default_state)
  { }

  bool forward(int letter) {
    if (!super::forward(letter))
      *this = def_state;
    return true;
  }

  self& operator= (const State &x) {
    super::operator=(x);
    return *this;
  }
};

// A substitute_cursor moves to default state when required transition is undefined
// and tries to move forward from this state. The default state is different for each
// state and is therefore stored in the state tag (cf. Aho & Corasick search algorithm).
//
// Instanciation parameters:
// 1. ForwardCursor: the cursor type to be adapted which is a model of the forward cursor concept.
//
// Requirements:
// None
//
// Warning: this could make the automaton cyclic. The forward method
// will stops only if the graph of the subsitute states is acyclic.
//
// TODO:
// What should be done for find and outgoing transitions traversal

template <class ForwardCursor>
class substitute_cursor : public ForwardCursor
{
public:
  typedef ForwardCursor               super;
  typedef substitute_cursor           self;
  typedef typename super::char_type   char_type;
  typedef typename super::state_type  state_type;
  typedef typename super::tag_type    tag_type;
  typedef typename super::char_traits char_traits;
  
  substitute_cursor(const ForwardCursor &x)
    : super(x)
  { }

  bool forward(const char_type& letter) {
    if (find(letter)) {
      forward();
      return true;
    }
    if (src_tag() != src()) {
      *this = src_tag();
      return !sink() && forward(letter);
    }
    return false;
  }

  self& operator=(const state_type &x) {
    super::operator=(x);
    return *this;
  }
};

// A few helper functions:
template <class Cursor>
inline
def_trans_cursor<Cursor> def_transc(const Cursor &x, int default_letter = 0) {
  return def_trans_cursor<Cursor>(x, default_letter);
}

template <class ForwardCursor>
inline
def_state_cursor<ForwardCursor> def_statec(const ForwardCursor &x, 
					   typename ForwardCursor::State p) 
{
  return def_state_cursor<ForwardCursor>(x, p);
}

template <class ForwardCursor>
inline
substitute_cursor<ForwardCursor> substitutec(const ForwardCursor &x) {
  return substitute_cursor<ForwardCursor>(x);
} 

ASTL_END_NAMESPACE

#endif // ASTL_DEFAULT_H