language.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_LANGUAGE_H
#define ASTL_LANGUAGE_H

#include <cursor.h>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

ASTL_BEGIN_NAMESPACE

// Name:                  language
// Category:              Algorithms
// Component Type:        Function
// Prototype:             See below
// Description:           Output the recognized language of a DFA
// Return value:          none
// Definition:            language.h
// Requirements on types: There must exist a conversion from char to OutputIterator::value_type 
// Preconditions:         [first, last) is a valid range. DFA must be acyclic.
// Complexity:            linear
// Example:               language.cc

template <class DepthFirstCursor>
void language(ostream &out,                                // where to write
	      DepthFirstCursor first,                      // start position
	      DepthFirstCursor last = DepthFirstCursor())  // stop condition
{
#ifndef _MSC_VER
  vector<typename DepthFirstCursor::Alphabet> word;
#else
  vector<DepthFirstCursor::Alphabet> word;
#endif
  for(word.reserve(16); first != last; ) {
    word.push_back(first.letter());
    if (first.aim_final()) {
#ifndef _MSC_VER
      for(typename vector<typename DepthFirstCursor::Alphabet>::const_iterator i =
#else
      for(typename vector<DepthFirstCursor::Alphabet>::const_iterator i =
#endif
	    word.begin(); i != word.end(); ++i)
	out << *i;
      out << endl;
    }
    while (!first.forward())  word.pop_back();
  }
}


#if !defined(_MSC_VER) && (!defined(__GNUG__) || __GNUG__ >= 3)
// g++ 2.96 does not see the previous template as a specialization of this one
// too bad: have to hide this more general version from g++ with version < 3
template <class OutputIterator, class DepthFirstCursor>
void language(OutputIterator out,                    // where to write
	      DepthFirstCursor first,                      // start position
	      DepthFirstCursor last = DepthFirstCursor())  // stop condition
{
  vector<typename DepthFirstCursor::Alphabet> word;
  for(word.reserve(16); first != last; ) {
    word.push_back(first.letter());
    if (first.aim_final()) {
      copy(word.begin(), word.end(), out);
      *out = '\n';
      ++out;
    }
    while (!first.forward())  word.pop_back();
  }
}
#endif

// Name:                  is_in
// Category:              Algorithms
// Component Type:        Function
// Prototype:             See below
// Description:           test if a word is in the recognized language of a DFA
// Return value:          true if the word has been recognized
// Definition:            language.h
// Requirements on types: first and last are models of input iterator. c is a model of cursor.
// Preconditions:         [first, last) is a valid range. c must point to a valid state.
// Complexity:            linear
// Example:               
// Notes:
// See also:

template <class InputIterator, class Cursor>
bool is_in(InputIterator first, InputIterator last, Cursor c)
{
  if (c.sink()) return false;
  while (first != last && c.forward(*first)) ++first;
  return first == last && c.src_final();
}

// Name:                 language_iterator
// Category:             Iterators
// Component Type:       Type
// Description:          An iterator whose value type is string. During traversal, the underlying
//                       cursor retrieves the recognized words of the DFA (depth-first search) and 
//                       stores the current one
//                       in a string of chars available through the dereferencement operator *
//                       (this is in fact an incremental version of the language algorithm above).
// Example:              
// Definition:           language.h
// Template parameters:  ForwardCursor = the type of the cursor to be used to access the DFA
// Model of:             Input iterator
// Type requirements:    
// Public base classes:  iterator<input_iterator_tag, string>
// Members:              
// New members:          
// Notes:                
// Bugs and limitations: The iterator outputs strings of ASCII chars. A more sophisticated alphabet
//                       will requires some extensions.
// See also:             algorithm language.

template <typename DFirstCursor>
#if (__GNUG__ && __GNUG__ < 3)
class language_iterator : public input_iterator<string, ptrdiff_t> 
#else
class language_iterator : public iterator<input_iterator_tag, string> 
#endif
{
protected:
  string current;
  DFirstCursor first, last;

public:
  typedef language_iterator self;

  language_iterator()      // end of range
    : first(), last()
  { }

  language_iterator(const DFirstCursor &x)     // beginning of range
    : first(x), last()
  { 
    if (first != last) {
      current += (char) first.letter();
      if (!first.aim_final()) ++*this;
    }
  }

  const DFirstCursor& cursor() const {
    return first;
  }

  const string& operator* () const {
    return current;
  }

  bool operator==(const self &x) const {
    return first == x.first;
  }

  bool operator!= (const self &x) const {
    return first != x.first;
  }
	
  self& operator++ () {
    while (1) 
      if (!first.forward())                      // ascending stage
	current.erase(current.size() - 1, 1);    // pop
      else
	if (first == last) return *this;
	else {
	  current += (char) first.letter();        // descending stage, push and test
	  if (first.aim_final()) return *this;
	}
    return *this;
  }
};

template <typename DFirstCursor>
inline
language_iterator<DFirstCursor> languagei(const DFirstCursor &x)
{
  return language_iterator<DFirstCursor>(x);
}

ASTL_END_NAMESPACE
		
#endif // ASTL_LANGUAGE_ALGORITHMS