lazy.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_LAZY_H
#define ASTL_LAZY_H

#include <map>
#include <utility>
#include <tools.h>
#include <cursor.h>

using namespace std;

ASTL_BEGIN_NAMESPACE

#ifndef TEMPLATE_TEMPLATE_IMPLEMENTATION
#define TEMPLATE_TEMPLATE_IMPLEMENTATION
#endif

// Defines:
// 1. lazy_cursor (cursor adapter)
// 2. lazy_cursor_tag

// A lazy cursor builds an automaton incrementally

// Instanciation parameters:
// 1. Cursor: the type of the cursor to be adapted
// 2. DFA: a ASTL DFA type
//
// Requirements:
// 1. The DFA Tag must be of type Cursor::State
//
// Constructors:
// 1. A cursor to be adapted, a DFA

#ifndef TEMPLATE_TEMPLATE_IMPLEMENTATION
template <class Cursor, class DFA>
class lazy_cursor : public cursor_concept
{
protected:
  typedef map<typename Cursor::state_type, safe<typename DFA::state_type, DFA::null_state> > mapper;
  Cursor c;
  DFA    *dfa;
  mapper mapping;
  safe<typename DFA::state_type, DFA::null_state> q;

public:
  typedef typename DFA::state_type     state_type;
  typedef typename Cursor::state_type  tag_type;
  typedef typename Cursor::char_type   char_type;
  typedef typename Cursor::char_traits char_traits;

  lazy_cursor(const Cursor &x, DFA &a)
    : c(x), dfa(&a), q(a.initial())
    { 
      if (q == DFA::null_state && !x.sink()) {
	q = dfa->new_state();
	dfa->tag(q) = c.src();
	mapping[c.src()] = q;
	dfa->final(q) = c.src_final();
	dfa->initial(q);
      }
    }

  state_type src() const {
    return q;
  }

  bool src_final() const {
    return dfa->final(q);
  }

  bool sink() const {
    return q == DFA::null_state;
  }

  bool forward(const char_type &a) {
    state_type tmp = dfa->delta1(q, a);
    if (tmp == DFA::null_state) {    // transition is not in the cache ?
      c = dfa->tag(q);
      if (c.forward(a)) {    // any transition labelled with 'a' ?
	safe<state_type, DFA::null_state> &tmp2 = mapping[c.src()];
	if (tmp2 == DFA::null_state) {   // not already been there ?
	  tmp2 = dfa->new_state();
	  dfa->final(tmp2) = c.src_final();
	  dfa->tag(tmp2) = c.src();
	  mapping[c.src()] = tmp2;
	}
	tmp = tmp2;
	dfa->set_trans(q, a, tmp);
      }
      else {
	q = DFA::null_state;
	return false;
      }
    }
    q = tmp;
    return true;
  }
};

// helper function
template <class Cursor, class DFA>
lazy_cursor<Cursor, DFA> lazyc(const Cursor &x, DFA &a) {
  return lazy_cursor<Cursor, DFA>(x, a);
}

#else
// - solution using template template: the user does not have to instanciate 
//   the DFA by himself, he only has to pass a template as argument for the cursor
//   template (the DFA must be instanciated with Tag == Cursor::state_type)
// - This implementation uses a smart pointer to reference the cache and the map 
//   between the visited states of the cursor and their copy in the cache for two 
//   reasons: 
//   1. We really need a constant time copy constructor
//   2. We want to keep the cache and the mapping as long as the lazy cursor is alive

#include <dfa_matrix.h>
#include <tools.h>
#include <tag.h>

template <class Cursor, template <class Sigma, class Tag> class DFA = DFA_matrix>
class lazy_cursor : public cursor_concept
{
public:
  typedef DFA<typename Cursor::char_traits, typename Cursor::state_type> DFA_type;

protected:
  typedef map<typename Cursor::state_type, 
    safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
  typename DFA_type::state_type my_sink;
  Cursor              c;
  smart_ptr<DFA_type> dfa;
  smart_ptr<mapper>   mapping;  
  safe<typename DFA_type::state_type, DFA_type::null_state> q;

public:
  typedef lazy_cursor                   self;
  typedef typename DFA_type::state_type state_type;
  typedef empty_tag                     tag_type;
  typedef typename Cursor::char_type    char_type;
  typedef typename Cursor::char_traits  char_traits;

  lazy_cursor(const Cursor &x)
    : c(x)
    { 
      if (!x.sink()) 
      {
	q = dfa->new_state();
	dfa->tag(q) = c.src();
	(*mapping)[c.src()] = q;
	dfa->final(q) = c.src_final();
	dfa->initial(q);
	my_sink = dfa->new_state();
      }
    }

  const DFA_type& cache() const {
    return *dfa;
  }

  state_type src() const {
    return q;
  }

  self& operator=(state_type p) {
    q = p;
    return *this;
  }

  bool src_final() const {
    return dfa->final(q);
  }

  empty_tag src_tag() const {
    return empty_tag();
  }

  bool sink() const {
    return q == DFA_type::null_state;
  }

  state_type sink_state() const {
    return DFA_type::null_state;
  }

  bool forward(const char_type &a) {
    state_type tmp = dfa->delta1(q, a);
    if (tmp == my_sink) {
      q = DFA_type::null_state;
      return false;
    }
    if (tmp == DFA_type::null_state)     // transition not in the cache ?
    {
      c = dfa->tag(q);
      if (c.forward(a))    // any transition labelled with 'a' ?
      { 
	safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
	if (tmp2 == DFA_type::null_state) {   // not already been there ?
	  tmp2 = dfa->new_state();
	  dfa->final(tmp2) = c.src_final();
	  dfa->tag(tmp2) = c.src();
	  (*mapping)[c.src()] = tmp2;
	}
	tmp = tmp2;
	dfa->set_trans(q, a, tmp);
      }
      else {
	dfa->set_trans(q, a, my_sink);
	q = DFA_type::null_state;
	return false;
      }
    }
    q = tmp;
    return true;
  }
};

template <class Cursor>
inline
lazy_cursor<Cursor> lazyc(const Cursor &c) {
  return lazy_cursor<Cursor>(c);
}

template <class Cursor, template <class Sigma, class Tag> class DFA = DFA_matrix>
class lazy_cursor_tag : public cursor_concept
{
public:
  typedef DFA<typename Cursor::char_traits, 
	      pair<typename Cursor::tag_type, typename Cursor::state_type> > DFA_type;

protected:
  typedef map<typename Cursor::state_type, 
    safe<typename DFA_type::state_type, DFA_type::null_state> > mapper;
  typename DFA_type::state_type my_sink;
  Cursor              c;
  smart_ptr<DFA_type> dfa;
  smart_ptr<mapper>   mapping;  
  safe<typename DFA_type::state_type, DFA_type::null_state> q;

public:
  typedef lazy_cursor_tag                   self;
  typedef typename DFA_type::state_type state_type;
  typedef typename Cursor::tag_type     tag_type;
  typedef typename Cursor::char_type    char_type;
  typedef typename Cursor::char_traits  char_traits;

  lazy_cursor_tag(const Cursor &x)
    : c(x)
    { 
      if (!x.sink()) 
      {
	q = dfa->new_state();
	dfa->tag(q).second = c.src();
	dfa->tag(q).first = c.src_tag();
	(*mapping)[c.src()] = q;
	dfa->final(q) = c.src_final();
	dfa->initial(q);
	my_sink = dfa->new_state();
      }
    }

  const DFA_type& cache() const {
    return *dfa;
  }

  state_type src() const {
    return q;
  }

  self& operator=(state_type p) {
    q = p;
    return *this;
  }

  bool src_final() const {
    return dfa->final(q);
  }

  tag_type src_tag() const {
    return dfa->tag(q).first;
  }

  bool sink() const {
    return q == DFA_type::null_state;
  }

  state_type sink_state() const {
    return DFA_type::null_state;
  }

  bool forward(const char_type &a) {
    state_type tmp = dfa->delta1(q, a);
    if (tmp == my_sink) {
      q = DFA_type::null_state;
      return false;
    }
    if (tmp == DFA_type::null_state)     // transition not in the cache ?
    {
      c = dfa->tag(q).second;
      if (c.forward(a))    // any transition labelled with 'a' ?
      { 
	safe<state_type, DFA_type::null_state> &tmp2 = (*mapping)[c.src()];
	if (tmp2 == DFA_type::null_state) {   // not already been there ?
	  tmp2 = dfa->new_state();
	  dfa->final(tmp2) = c.src_final();
	  dfa->tag(tmp2).second = c.src();
	  dfa->tag(tmp2).first = c.src_tag();
	  (*mapping)[c.src()] = tmp2;
	}
	tmp = tmp2;
	dfa->set_trans(q, a, tmp);
      }
      else {
	dfa->set_trans(q, a, my_sink);
	q = DFA_type::null_state;
	return false;
      }
    }
    q = tmp;
    return true;
  }
};

template <class Cursor>
inline
lazy_cursor_tag<Cursor> lazyc_tag(const Cursor &c) {
  return lazy_cursor_tag<Cursor>(c);
}

#endif // TEMPLATE_TEMPLATE_IMPLEMENTATION

ASTL_END_NAMESPACE
     
#endif // ASTL_CLASS_LAZY_CURSOR