ccopy.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_CCOPY_H
#define ASTL_CCOPY_H

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <tools.h>
#include <concept.h>
// #include <assert.h>

using namespace std;

ASTL_BEGIN_NAMESPACE

// Algorithm:   ccopy (cursor copy)
// Description: copy depth-first range [first, last) into a DFA during ascending
//              stage of the depth-first traversal triming uneeded paths
// Input:       two depth-first cursor and a DFA
// Output:      initial copied state
// Remark:      processing of the initial state is an external operation left up
//              to the user. The algorithm simply returns the upper copied
//              transition source state.
// Uses:        DFA::final(), DFA::set_trans(), DFA::new_state(), DFA::null_state

template <class DFirstCursor, class DFA>
typename DFA::state_type 
ccopy(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor())
{
  typedef map<typename DFirstCursor::state_type, 
				typename DFA::state_type> mapper;
  mapper mapping;
  typename DFirstCursor::state_type i = first.src();

  while (first != last) {     // while not end of range
    while(first.forward());   // get down as much as possible

    // copy aim state if final:
    typename DFA::state_type p;
    if (first.aim_final()) {
		typename mapper::iterator i = 
			mapping.insert(make_pair(first.aim(), DFA::null_state)).first;
		if (i->second == DFA::null_state) {   // inserted ?
//      safe<typename DFA::state_type, DFA::null_state> &dest = mapping[first.aim()];
 //     if (dest == DFA::null_state) {
	i->second = out.new_state();
	out.final(i->second) = true;
	//	out.tag(dest) = first.aim_tag();
      }
    }

    do { // while moving backward (pop) copy current
      // transition (q, first.letter(), p) 
      // copy source state if needed:
      typename mapper::const_iterator dest = mapping.find(first.aim());
      if (dest != mapping.end()) p = dest->second;
	  else p = DFA::null_state;
      
      if (p != DFA::null_state || first.src_final()) {
		  typename mapper::iterator i = mapping.insert(make_pair(first.src(), DFA::null_state)).first;
//	safe<typename DFA::state_type, DFA::null_state> &q = mapping[first.src()];
	if (i->second == DFA::null_state) {
	  i->second = out.new_state();
	  out.final(i->second) = first.src_final();
	  //	  out.tag(q) = first.src_tag();
	}
	// copy transition:
	if (p != DFA::null_state) 
	  out.set_trans(i->second, first.letter(), p);
	
	// shift (q, first.letter(), p) => (q', first.letter()', q)
	p = i->second;
      }
    } while (! first.forward());
  }
  return mapping[i];
}

// Algorithm:   clone
// Description: copy depth-first range [first, last) into a DFA in descending
//              stage of the depth-first traversal making thus an exact copy of
//              the compound
// Input:       two depth-first cursor and a DFA
// Output:      initial copied state
// Remark:      processing of the initial state is an external operation left up
//              to the user. The algorithm simply returns the first copied
//              transition source state.
// Uses:        DFA::final(), DFA::set_trans(), DFA::new_state(), DFA::null_state
  
template <class DFirstCursor, class DFA>
typename DFA::state_type 
clone(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor())
{
	if (first == last) return DFA::null_state;

#ifdef _MSC_VER
  // Because VC++6.0 has a non standard behavior and refuses 'typename' keyword here:
  typedef DFirstCursor::state_type cursor_state;
  typedef DFA::state_type          dfa_state;
#else
  typedef typename DFirstCursor::state_type cursor_state;
  typedef typename DFA::state_type          dfa_state;
#endif

  map<cursor_state, dfa_state> mapping;
  cursor_state i = first.src();
  dfa_state q;

  while (first != last) {     // while not end of range

    // copy source state if needed:
	  typename map<cursor_state, dfa_state>::iterator i 
		  = mapping.insert(make_pair(first.src(), DFA::null_state)).first;
    //safe<dfa_state, DFA::null_state> &source = mapping[first.src()];
	  if (i->second == DFA::null_state) {  // inserted ?
      i->second = out.new_state();
      out.final(i->second) = first.src_final();
      //      out.tag(source) = first.src_tag();
    }
    q = i->second;

    do {                      // while moving forward
      // copy current transition (q, first.letter(), p)
      // copy aim state if needed:
	  typename map<cursor_state, dfa_state>::iterator i 
		  = mapping.insert(make_pair(first.aim(), DFA::null_state)).first;

      //safe<dfa_state, DFA::null_state> &p = mapping[first.aim()];
      if (i->second == DFA::null_state) {
	i->second = out.new_state();
	out.final(i->second) = first.aim_final();
	//	out.tag(p) = first.aim_tag();
      }

      // copy transition:
      out.set_trans(q, first.letter(), i->second);
      // shift (q, first.letter(), p) => (p, first.letter()', p')
      q = i->second;
    } while (first.forward());

    while (!first.forward());   // pop
  }
  return mapping[i];
}

template <typename CharType>
struct read_char : public binary_function<istream, CharType, void>
{
  void operator()(istream &in, CharType& x) const {
    in >> x;
  }
};

template < >
struct read_char<unsigned char> 
  : public binary_function<istream, unsigned char, void>
{
  void operator()(istream &in, unsigned char& x) const {
    int tmp;
    in >> tmp;
    x = (unsigned char) tmp;
  }
};

template < >
struct read_char<char> 
  : public binary_function<istream, char, void>
{
  void operator()(istream &in, char& x) const {
    int tmp;
    in >> tmp;
    x = (char) tmp;
  }
};

template < >
struct read_char<string> 
  : public binary_function<istream, string, void>
{
  void operator()(istream &in, string& x) const {
    x.erase(x.begin(), x.end());   // VC++ does not implement clear()
    char c;
    for(; c != '"'; in.get(c));
    for(in.get(c); c != '"'; in.get(c))
      x += c;
  }
};


template <typename CharTraits>
class clone_cursor : public dfirst_cursor_concept
{
public:
  typedef CharTraits                     char_traits;
  typedef typename CharTraits::char_type char_type;
  typedef int                            state_type;
  typedef empty_tag                      tag_type;

  // Backward compatibility:
  typedef state_type State;
  typedef tag_type   Tag;
  typedef char_type  Alphabet;
  typedef CharTraits Sigma;

protected:
  struct transition 
  {
    state_type q, p;
    char_type a;
    bool operator==(const transition &x) const {
      return q == x.q && p == x.p && a == x.a;
    }
  };

  istream &in;
  stack<transition> s;
  transition t;
  bool has_poped;

public:
  typedef clone_cursor self;

  clone_cursor()               // end of range
    : in(cin)
  { }

  clone_cursor(istream &input) // start of range
    : in(input), has_poped(false) {
    forward();
  }

  state_type src() const {
    return s.top().q;
  }

  state_type aim() const {
    assert(!s.empty());
    return s.top().p;
  }

  bool operator==(const self &x) const { // to test for the end of range
    return s == x.s;
  }

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

  bool src_final() const {
    return s.top().q < 0;
  }

  bool aim_final() const {
    return s.top().p < 0;
  }

  char_type letter() const {
    return s.top().a;
  }

  bool forward() 
  {
    if (in.eof()) {
      s.pop();
      return s.empty();
    }

    if (has_poped) {
      if (s.top().q == t.q) {
	s.top() = t;
	has_poped = false;
      }
      else 
	s.pop();
    }
    else {
      in >> t.q;
#if defined(__GNUG__) && __GNUG__ >= 3
      if (in.eof())
	return false;
#endif
      read_char<char_type>()(in, t.a);
      in >> t.p;
      if (s.empty() || s.top().p == t.q) {
	s.push(t);
      }
      else 
	has_poped = true;
    }
    return !has_poped;
  }

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

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

ASTL_END_NAMESPACE

#endif