dfa_compact.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_COMPACT_H
#define ASTL_DFA_COMPACT_H

// Descrition:	  
//   ASTL 2.0 Determinisic Finite Automaton Class Template DFA_compact
//   Compact Representation with a single transition array 
//  

#ifndef _MSC_VER
#include <unistd.h>   // close(int)
#include <sys/mman.h>  // mmap
#include <fcntl.h>     // read
#include <errno.h>
#else
#define min _MIN
#endif

#include <vector>
#include <utility>     // pair<>
#include <functional>  // identity<>
#include <astl.h>
#include <concept.h>
#include <tools.h>     // mapable_vector<>

ASTL_BEGIN_NAMESPACE

// ** WARNING: to be able to use tags and the binary save/load
// functionality (along side memory mapping), the tag type MUST BE A POD TYPE **

// Implementation notes
// This representation makes use of 4 arrays:
// 1. vector v1 for transitions labels (value_type == DFA::Alphabet)
// 2. vector v2 for transitions aims (value_type == unsigned long)
// 3. a bit vector for final states flags
// 4. vector of tags

// A matrix cell is made of two cells from vectors v1 and v2.
// if (v1[n] == 0) then there is no transition is this cell
//   then if (v2[n] != 0) then v2[n] is the tag index for the state in cell n+1
//   else the cell is free
// else v1[n] is the transition label and v2[n] is the transition target


// Object function reading & writing on binary streams
// To be used with STL algorithm for_each
template <class Tag>
struct tag_save : unary_function<Tag, void>
{
  ostream &out;
  tag_save(ostream &x) : out(x) 
  { }
  void operator()(const Tag &x) {
    out.write((const char *)&x, sizeof(x));
  }
};

template <class Tag>
struct tag_load : unary_function<Tag, void>
{
  istream &in;
  tag_load(istream &x): in(x)
  { }
  void operator()(Tag &x) {
    in.read(&x, sizeof(x));
  }
};


#ifdef __GNUG__
#if (__GNUG__ < 3)
template <class DFA, class tag_mapping = identity<typename DFA::Tag> >
#else
template <class DFA, class tag_mapping = __gnu_cxx::identity<typename DFA::Tag> >
#endif
#else
#ifdef _MSC_VER
template <class DFA, class tag_mapping = identity<DFA::Tag> >
#else
template <class DFA, class tag_mapping = identity<typename DFA::Tag> >
#endif
#endif

class DFA_compact : public DFA_concept
{
public:
  typedef typename DFA::char_traits         char_traits;
  typedef typename DFA::char_type           char_type;
  typedef unsigned long                     state_type;
  typedef typename tag_mapping::result_type tag_type;
 
  // Backward compatibility:
  typedef char_traits Sigma;
  typedef char_type   Alphabet;
  typedef tag_type    Tag;
  typedef state_type  State;

private:
  typedef mapable_vector<int>::size_type size_type;
  typedef mapable_vector<bool> set_F;
  typedef DFA_compact self;

public:
#if (__GNUG__ && __GNUG__ < 3)
  class const_iterator : public forward_iterator<state_type, ptrdiff_t>
#else
  class const_iterator : public iterator<forward_iterator_tag, state_type>
#endif
  {
    friend class DFA_compact<DFA, tag_mapping>;
  private:
    state_type state;
    const mapable_vector<char_type> *ml;
    const mapable_vector<state_type> *ma;

    const_iterator(state_type x, const mapable_vector<char_type> *a, 
		   const mapable_vector<state_type> *s) 
      : state(x), ml(a), ma(s) { }    

  public:

    const_iterator() : ml(NULL), ma(NULL) { }
    state_type operator * () const { return (state); }
    const_iterator& operator ++ ()
    {
      for (; state < ml->size(); ++state)
	{
	  if ((*ml)[state] == (char_type) 0 && (*ma)[state] != 0)   // this is a cell holding a tag index
	    {
	      ++state;                                // there is a state after a tag
	      break;
	    }
	}
      return (*this);
    }
    const_iterator operator ++ (int)
    {
      const_iterator tmp = *this;
      ++(*this);
      return (tmp);
    }
    const_iterator& operator = (const const_iterator &x) 
    {
      state = x.state;
      ml = x.ml;
      ma = x.ma;
      return (*this);
    }
    bool operator == (const const_iterator &x) const {
      return (state == x.state);
    }
    bool operator != (const const_iterator &x) const {
      return (!(*this == x));
    }
  };

  class edges_type
  {
  private:
    state_type                s;
    const mapable_vector<char_type>   *ml;
    const mapable_vector<state_type> *ma;

  public:
    edges_type(state_type st, const mapable_vector<char_type> &l, 
	       const mapable_vector<state_type> &a) 
      : s(st), ml(&l), ma(&a) { }

    typedef char_type Key;
    typedef pair<const Key, state_type> value_type;
    typedef less<char_type> key_compare;

    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef state_type size_type;
    typedef typename DFA::edges_type::difference_type difference_type;
    
    class value_compare : public binary_function<value_type, value_type, bool>
    {
      friend class edges_type;
      
    protected:
      key_compare comp;
      value_compare(key_compare c) : comp(c) { }
      
    public:
      bool operator () (const value_type& x, const value_type& y) {
	return (comp(x.first, y.first));
      }
    };

#if (__GNUG__ && __GNUG__ < 3)
    class const_iterator : bidirectional_iterator<value_type, ptrdiff_t>
#else
    class const_iterator : iterator<bidirectional_iterator_tag, value_type>
#endif
    {
#ifndef _MSC_VER
      friend class DFA_compact<DFA, tag_mapping>::edges_type;
#else
	  public:
#endif

      const mapable_vector<char_type>  *ml;
      const mapable_vector<state_type> *ma;
      state_type                       state;
      size_type                        pos;

      const_iterator(state_type s, const mapable_vector<char_type> &l, 
		     const mapable_vector<state_type> &a, size_type _pos = 0)
	: ml(&l), ma(&a), state(s), pos(_pos) { }

    public:
#ifndef _MSC_VER
	  typedef edges_type::value_type value_type;
#else
	  typedef pair<char_type, state_type> value_type;
#endif

      const_iterator() { }
      const_iterator(const const_iterator& i) 
	: ml(i.ml), ma(i.ma), state(i.state), pos(i.pos) 
      { }

      bool operator == (const const_iterator &x) const {
	return (pos == x.pos && state == x.state); /// && ml == x.ml && ma == x.ma);
      }

      const_iterator::value_type operator * () const {
	return const_iterator::value_type((*ml)[state + pos], 
					  (*ma)[state + pos]);
      }

      const_iterator& operator ++ ()
      {
	size_t max_offset = (size_t)
	  min((size_type) (ml->size() - state), (size_type) self::char_traits::size);
	for (++pos; pos < max_offset; ++pos)
	  if ((*ml)[state + pos] != (char_type) 0 &&
	      (size_t) self::char_traits::to_int_type((*ml)[state + pos]) == pos)
	      break;
	return (*this);
      }
      const_iterator operator ++ (int)
      {
	const_iterator tmp = (*this);
	++(*this);
	return tmp;
      }
      const_iterator& operator -- ()
      {
	for (--pos; pos != 0; --pos)
	  if (self::char_traits::to_int_type((*ml)[state + pos]) == pos) 
	    break;
	return (*this);
      }
      const_iterator operator -- (int)
      {
	const_iterator tmp = (*this);
	--(*this);
	return tmp;
      }
    };

    // Back to edges_type class

    typedef const_iterator iterator;

    edges_type() : s((state_type) 0), ml(NULL), ma(NULL) { }

    key_compare key_comp() const
    { 
      key_compare tmp;
      return (tmp); 
    }

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

    state_type operator [] (const Key& k) const
    {
		state_type q = s + self::char_traits::to_int_type(k);
      if ((*ml)[q] == k)
	return ((*ma)[q]);
      else
	return ((state_type) 0);
    }

    const_iterator begin() const
    {
		typename self::char_traits::int_type offset;
		typename self::char_traits::int_type max_offset = 
			min((size_type) (ml->size() - s), (size_type) self::char_traits::size);

      // Looking for the first transition of the state
      for (offset = 0; offset < max_offset; ++offset)
	if ((*ml)[s + offset] != (char_type) 0)
		if (self::char_traits::to_int_type((*ml)[s + offset]) == offset)
	    break;

      return const_iterator(s, *ml ,*ma, offset);
    }

    const_iterator end() const {
      return const_iterator(s, *ml , *ma, min((size_type) (ml->size() - s), 
		  (size_type) self::char_traits::size));
    }
    size_type size() const
    {
		typename self::char_traits::int_type offset;
		typename self::char_traits::int_type result = 0;
      size_type max_offset = min((size_type) (ml->size() - s), 
		  (size_type) self::char_traits::size);

      for (offset = 0; offset < max_offset; ++offset) {
		  if (self::char_traits::to_int_type((*ml)[s + offset]) == offset)
	  ++result;
      }
      return (result);
    }

    bool empty() const {
      return (size() == 0);
    }

    iterator find(const Key &k) const
    {
		long mapped = self::char_traits::to_int_type(k);
      state_type result = s + mapped;
      if (result < ml->size())
	if ((*ml)[result] == k)
	  return (iterator(s, *ml, *ma, mapped));