astl2.tex

一个类似STL的自动机的源代码库

  make_hash(A);
  const char *word = ``word'';
  std::cout << hash_value(forwardc(A), word, word + 4) << std::endl;
  std::string s;
  value_hash(forwardc(A), 14, std::back_inserter(s));
} 
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item The requirement that \verb+DFA::tag_type+ be
  \verb+hash_tag+ is a minimal assumption. The tag type can be
  {\em anything} provided that it is {\em at least} a \verb+hash_tag+.
\item The DFA must stores the transitions in sorted containers which
  means that this algorithm can not be used on containers
  \verb+DFA_mtf+, \verb+DFA_hash+ and \verb+DFA_tr+.
\item A DFA must be rehashed each time it undergoes any
  modifications. 
\end{itemize}
\paragraph{See Also \\}
\verb+hash_cursor+, \verb+hash_value+, \verb+value_hash+.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% HASH_VALUE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf hash\_value}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename ForwardCursor, typename InputIterator>
int hash_value(ForwardCursor c, InputIterator first, InputIterator last);
\end{verbatim}
\paragraph{Description \\}
Returns the positive integer hash value associated to the sequence of
characters \verb+[first, last)+ by the hashing automaton pointed to by
\verb+c+. A null value is returned if the word is not recognized by
the automaton. 
\paragraph{Definition \\}
\verb+hash.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+ForwardCursor+ is a model of forward cursor.
\item \verb+InputIterator+ is a model of input iterator.
\item \verb+InputIterator::value_type+ is convertible to
  \verb+ForwardCursor::char_type+.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\item \verb+c+ points to a hashing automaton constructed with the
  algorithm \verb+make_hash+.
\item \verb+c+ points to the initial state of the hashing automaton. 
\end{itemize}
\paragraph{Complexity \\}
\verb+last - first+ calls to \verb+ForwardCursor::forward+.
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <hash.h>
#include <iostream>
#include <cassert>

int main()
{
  DFA_matrix<plain, hash_tag> A;
  make_hash(A);
  const char *word = ``word'';
  std::cout << hash_value(forwardc(A), word, word + 4) << std::endl;
} 
\end{verbatim}
\paragraph{See Also \\}
\verb+make_hash+, \verb+value_hash+
%%%%%%%%%%%%%%%%%%%%%%%%%%% VALUE_HASH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf value\_hash}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename ForwardCursor, typename OutputIterator>
int value_hash(ForwardCursor c, int i, OutputIterator x);
\end{verbatim}
\paragraph{Description \\}
Returns the word associated to the positive integer \verb+i+ by the
hashing automaton pointed to by \verb+c+. The returned word is copied
to the output sequence pointed by \verb+x+ and the function returned
value is its length. 
\paragraph{Definition \\}
\verb+hash.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+ForwardCursor+ is a model of forward cursor.
\item \verb+OutputIterator+ is a model of output iterator.
\item \verb+ForwardCursor::char_type+ is convertible to
  \verb+OutputIterator::value_type+.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+c+ points to a hashing automaton constructed with the
  algorithm \verb+make_hash+.
\item \verb+c+ points to the initial state of the hashing automaton.
\item \verb+i+ is a strictly positive integer.
\item There is enough space to hold all of the elements being copied.
\end{itemize}
\paragraph{Complexity \\}
Linear in the length of the output word.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+make_hash+, \verb+hash_value+
%%%%%%%%%%%%%%%%%%%%%%%%%%% FIRST_MATCH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf first\_match}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename ForwardIterator, typename Cursor>
ForwardIterator 
first_match(ForwardIterator first, ForwardIterator last, Cursor &c);
\end{verbatim}
\paragraph{Description \\}
Returns a past-the-end iterator on the shortest prefix of the word 
\verb+[first, last)+ recognized by the automaton pointed by
\verb+c+. If none is found, \verb+first+ is returned which means that
either no final state has been reached during the traversal or a
transition was undefined.
\paragraph{Definition \\}
\verb+match.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+ForwardIterator+ is a model of forward iterator.
\item \verb+Cursor+ is a model of plain cursor.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear: at most \verb+last - first+ calls to \verb+Cursor::forward+.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+longest_match+, \verb+match_count+
%%%%%%%%%%%%%%%%%%%%%%%% LONGEST_MATCH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf longest\_match}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <class ForwardIterator, class Cursor>
ForwardIterator 
longest_match(ForwardIterator first, ForwardIterator last, Cursor &c);
\end{verbatim}
\paragraph{Description \\} 
Returns a past-the-end iterator on the longest prefix of the word 
\verb+[first, last)+ recognized by the automaton pointed by
\verb+c+. If none is found, \verb+first+ is returned which means that
either no final state has been reached during the traversal or a
transition was undefined.
\paragraph{Definition \\}
\verb+match.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+ForwardIterator+ is a model of forward iterator.
\item \verb+Cursor+ is a model of plain cursor.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear: at most \verb+last - first+ calls to \verb+Cursor::forward+.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+first_match+, \verb+match_count+
%%%%%%%%%%%%%%%%%%%%%%%%% LANGUAGE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf language}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFirstCursor>
void language(ostream &out,                              
              DFirstCursor first, DFirstCursor last = DFirstCursor());
\end{verbatim}
\paragraph{Description \\}
Output to \verb+out+ the language recognized by the DFA defined by
the range \verb+[first, last)+.
\paragraph{Definition \\}
\verb+language.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFirstCursor+ is a model of depth-first cursor.
\item \verb+operator<<(ostream&, DFirstCursor::char_type)+ is
  defined. 
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+language_iterator+
%%%%%%%%%%%%%%%%%%%%%%%%%%% IS_IN %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf is\_in}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename InputIterator, typename Cursor>
bool is_in(InputIterator first, InputIterator last, Cursor c);
\end{verbatim}
\paragraph{Description \\}
Returns \verb+true+ if the word \verb+[first, last)+ is in the
language recognized by the DFA pointed by \verb+c+.
\paragraph{Definition \\}
\verb+language.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+InputIterator+ is a model of input iterator.
\item \verb+Cursor+ is a model of plain cursor.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear: at most \verb+last - first+ calls to \verb+Cursor::forward+.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+first_match+, \verb+longest_match+
%%%%%%%%%%%%%%%%%%%%%%%%%%% MATCH_COUNT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf match\_count}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename InputIterator, typename Cursor>
int match_count(InputIterator first, InputIterator last, Cursor &c);
\end{verbatim}
\paragraph{Description \\} 
Returns the number of prefixes of the word \verb+[first, last)+
recognized by the DFA pointed to by \verb+c+, in other words, the
number of final states \verb+c+ has reached along the path labelled
with \verb+[first, last)+.
\paragraph{Definition \\}
\verb+match.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+InputIterator+ is a model of input iterator.
\item \verb+Cursor+ is a model of plain cursor.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear: at most \verb+last - first+ calls to \verb+Cursor::forward+.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\paragraph{See Also \\}
\verb+first_match+, \verb+longest_match+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ISOMORPH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf isomorph}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFirstCursor1, typename DFirstCursor2>
bool isomorph(DFirstCursor1 left, DFirstCursor2 first, 
              DFirstCursor2 last = DFirstCursor2());
\end{verbatim}
\paragraph{Description \\} 
Returns \verb+true+ if the DFA defined by the range 
\verb+[left, DFirstCursor1())+ is isomorphic to the DFA defined by
\verb+[first, last)+. 
\paragraph{Definition \\}
\verb+set_operation.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFirstCursor1+ is a model of depth-first cursor.
\item \verb+DFirstCursor2+ is a model of depth-first cursor.
\item \verb+DFirstCursor2::char_type+ is convertible to
  \verb+DFirstCursor1::char_type+.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[left, DFirstCursor1())+ is a valid range.
\item \verb+[first, last)+ is a valid range.
\end{itemize}
\paragraph{Complexity \\}
Linear
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TREE_BUILD %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf add\_word, add\_words}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large Algorithm}} & \flushright {\bf Component Type :
{\Large Function}} 
\end{tabular} \\
\paragraph{Prototype}
\begin{verbatim}
template <typename DFA1, typename InputIterator1>
void add_word(DFA1 &a, InputIterator1 first, InputIterator1 last, 
              const DFA1::tag_type &t = DFA1::tag_type());

template <typename DFA2, typename InputIterator2>
void add_words(DFA2 &a, InputIterator2 start, InputIterator2 finish);
\end{verbatim}
\paragraph{Description \\}
\verb+add_word+ adds the word \verb+[first, last)+ to the language
recognized by \verb+a+. The tag \verb+t+ is assigned to the newly
created final state. \verb+add_words+ adds a set of words to the
language, which means \verb+start+ points to containers of
characters. \verb+a+ must have a tree structure.
\paragraph{Definition \\}
\verb+astl_tree.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+InputIterator1+ and \verb+InputIterator2+ are models of
  input iterator.
\item \verb+DFA1+ and \verb+DFA2+ are models of DFA.
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+a+ has a tree structure, it must not be cyclic nor have a
  DAG (Directed Acyclic Graph) structure.
\item \verb+[first, last)+ is a valid range.
\item \verb+InputIterator1::value_type+ is convertible to
  \verb+DFA1::char_type+.
\item \verb+[start, finish)+ is a valid range.
\item \verb+InputIterator2::value_type+ is a container whose
  \verb+value_type+ is \verb+DFA2::char_type+.
\end{itemize}
\paragraph{Complexity \\}
\verb+add_word+: \verb+last - first+ calls to \verb+DFA::delta1+ or
\verb+DFA1::set_trans+. \\
\verb+add_words+: \verb+finish - start+ calls to \verb+add_word+.
\paragraph{Example}
\begin{verbatim}
\end{verbatim}
\section{Advanced Examples}
\end{document}