match.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_MATCH_H
#define ASTL_MATCH_H

#include <astl.h>

ASTL_BEGIN_NAMESPACE

// Returns a past-the-end iterator on the shortest matching subsequence of [first, last). 
// If none is found, first is returned.

// Category:       Algorithms
// Component Type: Function
// Prototype:
// template <class ForwardIterator, class Cursor>
// ForwardIterator first_match(ForwardIterator first, ForwardIterator last, Cursor c)
//
// Description:   first_match looks for the shortest subsequence of [first, last) starting
//                at first and recognized by the DFA accessed through the cursor c.
// Return value:  first_match returns a past-the-end iterator on the matching subsequence. 
//                If none is found, first is returned which means that either no final state
//                has been reached during the traversal or a transition was undefined.
// Definition:    matcher.h
// Requirements on types: 
//                - ForwardIterator is a model of forward iterator
//                - Cursor is a model of plain cursor
//                - forward iterator value type must be convertible to Cursor::Alphabet
// Preconditions: c must have a non singular value, however c might point to the sink state.
// Complexity:    at most (last - first) calls to the transition function Cursor::forward
// Notes:         this algorithm ignores the empty word.
// Bugs and limitations:
// See also: longest_match, match_count

template <class ForwardIterator, class Cursor>
inline
ForwardIterator 
first_match(ForwardIterator first, const ForwardIterator &last, Cursor &c)
{
  if (c.sink()) return first;
  ForwardIterator start = first;
  for(; first != last && c.forward(*first); ++first)
    if (c.src_final()) return ++first;
  return start;  // no match found
}

template <class ForwardIterator, class Cursor>
inline
ForwardIterator 
first_match(ForwardIterator first, const ForwardIterator &last, const Cursor &c)
{
  Cursor tmp = c;
  return first_match(first, last, tmp);
}

// Category:       Algorithms
// Component Type: Function
// Prototype:
// template <class ForwardIterator, class Cursor>
// ForwardIterator longest_match(ForwardIterator first, ForwardIterator last, Cursor c)
//
// Description:   longest_match looks for the longest subsequence of [first, last) starting
//                at first and recognized by the DFA accessed through the cursor c.
// Return value:  longest_match returns a past-the-end iterator on the matching subsequence. 
//                If none is found, first is returned which means that either no final state
//                has been reached during the traversal or an undefined transition has been
//                accessed before reaching any final state.
// Definition:    matcher.h
// Requirements on types: 
//                - ForwardIterator is a model of forward iterator
//                - Cursor is a model of plain cursor
//                - forward iterator value type must be convertible to Cursor::Alphabet
// Preconditions: c must have a non singular value, however c might point to the sink state.
// Complexity:    at most (last - first) calls to the transition function Cursor::forward
// Notes:         this algorithm ignores the empty word.
// See also: longest_match, match_count

template <class ForwardIterator, class Cursor>
inline
ForwardIterator 
longest_match(ForwardIterator first, const ForwardIterator &last, Cursor &c)
{
  if (c.sink()) return first;
  ForwardIterator last_match_position = first;
  while(first != last && c.forward(*first)) {
    ++first;
    if (c.src_final()) 
      last_match_position = first;
  }
  return last_match_position;
}

template <class ForwardIterator, class Cursor>
inline
ForwardIterator 
longest_match(ForwardIterator first, const ForwardIterator &last, const Cursor &c)
{
  Cursor tmp = c;
  return longest_match(first, last, tmp);
}

// Category:       Algorithms
// Component Type: Function
// Prototype:
// template <class InputIterator, class Cursor>
// unsigned int match_count(InputIterator first, InputIterator last, Cursor c)
//
// Description:
// Return value:
// Definition:
// Requirements on types:
// Preconditions:
// Complexity:
// Example:
// Notes:         this algorithm ignores the empty word.    
// Bugs and limitations:
// See also: first_match, longest_match

template <typename InputIterator, typename Cursor>
inline
int match_count(InputIterator first, InputIterator last, Cursor &c)
{
  if (c.sink()) return 0;
  int r = 0;
  for(; first != last && c.forward(*first); ++first)
    if (c.src_final()) ++r;
  return r;
}

template <class InputIterator, class Cursor>
inline
unsigned int 
match_count(InputIterator first, InputIterator last, const Cursor &c)
{
  Cursor tmp = c;
  return match_count(first, last, tmp);
}

// Category:       Algorithms
// Component Type: Function
// Prototype:
// template <class InputIterator, class Cursor>
// bool match(InputIterator first, InputIterator last, Cursor c)
//
// Description:
// Return value:
// Definition:
// Requirements on types:
// Preconditions:
// Complexity:
// Example:
// Notes:         this algorithm ignores the empty word.    
// Bugs and limitations:
// See also: first_match, longest_match

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

template <class InputIterator, class Cursor>
inline
bool match(InputIterator first, InputIterator last, const Cursor &c)
{
  Cursor tmp = c;
  return match(first, last, tmp);
}

ASTL_END_NAMESPACE

#endif