astl2.tex

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

\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|p{6.5cm}|p{4.5cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+ForwardCursor+ & The type of the cursors which are stored in the
stack & \\ \hline
\verb+Container+ & The type of the sequential container implementing the stack &
\verb+vector<ForwardCursor>+ \\ \hline 
\end{tabular}
\paragraph{Model of \\}
plain cursor, forward cursor, stack cursor.
\paragraph{Type requirements \\}
\begin{itemize}
\item \verb+ForwardCursor+ is a model of forward cursor.
\item \verb+Container+ is a model of back insertion sequence.
\item \verb+Container::value_type+ must be \verb+ForwardCursor+.
\end{itemize}
\paragraph{Public base classes \\}
\verb+cursor_concept+, \verb+forward_cursor_concept+, \verb+stack_cursor_concept+.
\paragraph{Members \\ [1ex]}
\begin{longtable}[h]{|l|p{1.3cm}|p{5.8cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{forward_cursor}
\verb+bool backward()+ & stack cursor & pop the stack top. Return
\verb+false+ if the resulting stack is empty. \\ \hline
\end{longtable}
\paragraph{New Members \\ [1ex]}
\begin{tabular}{|l|p{7cm}|} \hline
\bf Membre & \bf Description \\ \hline
\verb+stack_cursor(const ForwardCursor &c)+ & Construct a stack cursor
with a stack containing \verb+c+. \\ \hline
\verb+stack_cursor()+ & Construct a stack cursor
with an empty stack.\\ \hline
\end{tabular}
\paragraph{Helper Functions \\}
\begin{verbatim}
template <class ForwardCursor>
stack_cursor<ForwardCursor> stackc(const ForwardCursor &x);
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item Calls to the \verb+stack_cursor+ methods are only valid iff the stack
is non-empty.
\item The default constructor is used by the depth-first cursor
  to implement ends of range: the empty stack serves as stop condition
  for the traversal.
\end{itemize}
\paragraph{See Also \\}
forward cursor, stack cursor, depth-first cursor, \verb+dfirst_cursor+.

%%%%%%%%%%%%%%%%%%%%%%%%% QUEUE_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf queue\_cursor$<$ForwardCusor, Container$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+queue_cursor+ is a forward cursor storing its path in a queue
of cursors. Each move through the sequence of the outgoing transitions
of the source state (\verb+next_transition+) enqueues a forward
cursor. An extra method \verb+dequeue+ allows to dequeue and to
implement the breadth-first traversal. 
%\paragraph{Example}
%\begin{verbatim}
%@@@Example
%\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|p{7cm}|p{4cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+ForwardCursor+ & The type of the cursors stored in the queue & \\ \hline
\verb+Container+ & The type of the sequential container implementing
the queue & \verb+deque<ForwardCursor>+ \\ \hline
\end{tabular}
\paragraph{Model of \\}
plain cursor, forward cursor, queue cursor.
\paragraph{Type requirements \\}
\begin{itemize}
\item \verb+ForwardCursor+ is a model of forward cursor.
\item \verb+Container+ is a model of front insertion sequence. 
\item  \verb+Container::value_type+ must be \verb+ForwardCursor+.
\end{itemize}
\paragraph{Public base classes \\}
\verb+cursor_concept+, \verb+forward_cursor_concept+, \verb+queue_cursor_concept+.
\paragraph{Members \\ [1ex]}
\begin{longtable}[h]{|l|p{1.3cm}|p{5.8cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{forward_cursor}
\verb+bool dequeue()+ & queue cursor & dequeue the current cursor and
return \verb+false+ is the resulting queue is empty \\ \hline
\end{longtable}
\paragraph{New Members \\ [1ex]}
\begin{tabular}{|l|p{7cm}|} \hline
\bf Membre & \bf Description \\ \hline
\verb+queue_cursor(const ForwardCursor &c)+ & Construct a cursor with
a queue storing \verb+c+. \\ \hline
\verb+queue_cursor()+ & Construct a cursor with an empty queue. \\ \hline
\end{tabular}
\paragraph{Helper Functions \\}
\begin{verbatim}
template <class ForwardCusor>
queue_cursor<ForwardCusor> queuec(const ForwardCusor &x);
\end{verbatim}
\paragraph{Notes}
\begin{itemize}
\item Calls to the \verb+queue_cursor+ methods are only valid iff the queue
is non-empty.
\item The default constructor is used by the breadth-first cursor
  to implement ends of range: the empty queue serves as stop condition
  for the traversal.
\end{itemize}
\paragraph{See Also \\}
forward cursor, queue cursor, breadth-first cursor, \verb+bfirst_cursor+.

%%%%%%%%%%%%%%%%%%%%%%%%% DFIRST_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf dfirst\_cursor$<$StackCursor$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+dfirst_cursor+ implements the depth-first traversal on acyclic
deterministic automata. It is in
some sense an iterator on a sequence of transitions ordered according
to the depth-first traversal algorithm. The method \verb+forward+
allows to increment the cursor, making it point to the next transition
in the sequence. This methods returns \verb+true+ if the transition
reached has been pushed onto the stack (forward move) and \verb+false+
otherwise (pop and backward move). \\
The \verb+dfirst_cursor+ is fundamental because it is used much in the
same way as the iterators on sequence to define ranges for
algorithms. 
\paragraph{Example}
\begin{verbatim}
string w[4] = { "forward", "cursor", "code", "example" };
DFA_bin a;
tree_build(a, w, w + 4);
dfirst_cursor<stack_cursor<forward_cursor<DFA_bin<> > > >
  first = dfirstc(a), last;
vector<char> word;
while (first != last) {
  do {
    word.push_back(first.letter());
    if (first.aim_final()) {
      copy(word.begin(), word.end(), ostream_iterator<char>(cout));
      cout << endl;
    }
  } while (first.forward());

  while (!first.forward()) word.pop_back();
}
\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|l|l|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+StackCursor+ & The type of the underlying stack cursor & \\
\hline 
\end{tabular}
\paragraph{Model of \\}
depth-first cursor.
\paragraph{Type requirements \\}
\begin{itemize}
\item \verb+StackCursor+ is a model of stack cursor.
\end{itemize}
\paragraph{Public base classes \\}
\verb+dfirst_cursor_concept+.
\paragraph{Members \\ [1ex]}
\begin{longtable}{|p{5.5cm}|p{1.7cm}|p{6.5cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{dfirst_cursor}
\end{longtable}
\paragraph{New Members \\ [1ex]}
\begin{tabular}{|l|p{7cm}|} \hline
\bf Membre & \bf Description \\ \hline
\verb+dfirst_cursor(const StackCursor &c)+ & Construct a cursor with
\verb+c+ as stack. \\ \hline
\end{tabular}
\paragraph{Helper Functions \\}
The function \verb+dfirstc+ returns a \verb+dfirst_cursor+ constructed
from the object passed as argument. This object is allowed to be a
model of DFA, forward cursor or stack cursor.
\paragraph{Notes}
\begin{itemize}
\item Calls to method other than \verb+operator==+ are valid iff the cursor
stack is non-empty.
\item This cursor works only on acyclic structures, use
  \verb+dfirst_mark_cursor+ on cyclic DFAs.
\end{itemize}
\paragraph{See Also \\}
depth-first cursor, stack cursor, \verb+dfirst_mark_cursor+.

%%%%%%%%%%%%%%%%%%%%%%%%% DFIRST_MARK_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf dfirst\_mark\_cursor$<$StackCursor, Marker$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+dfirst_mark_cursor+ implements the depth-first traversal on cyclic
deterministic automata. It works exactly as the \verb+dfirst_cursor+
does except that a state-mark function garantees that each transition
is only reached twice
%\paragraph{Example}
%\begin{verbatim}
%@@@Example
%\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|l|p{5cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+StackCursor+ & The type of the underlying stack cursor & \\ \hline
\verb+Marker+ & The type of the state-mark object function & \verb+set_marker+ \\ \hline
\end{tabular}
\paragraph{Model of \\}
depth-first cursor.
\paragraph{Type requirements \\}
\begin{itemize}
\item \verb+StackCursor+ is a model of stack cursor.
\item \verb+Marker+ is a model of state marker.
\end{itemize}
\paragraph{Public base classes \\}
\verb+dfirst_cursor_concept+.
\paragraph{Members \\}
\begin{longtable}{|p{5.5cm}|p{1.7cm}|p{6.5cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{dfirst_cursor}
\end{longtable}
\paragraph{New Members \\ [1ex]}
\begin{tabular}{|l|p{7cm}|} \hline
\bf Membre & \bf Description \\ \hline
\verb+dfirst_cursor(const StackCursor &c)+ & Construct a cursor with
\verb+c+ as stack. \\ \hline
\end{tabular}
\paragraph{Helper Functions \\}
The function \verb+dfirst_markc+ returns a \verb+dfirst_mark_cursor+ constructed
from the object passed as argument. This object is allowed to be a
model of DFA, forward cursor or stack cursor.
\paragraph{Notes}
\begin{itemize}
\item Calls to method other than \verb+operator==+ are valid iff the cursor
stack is non-empty.
\item This cursor is designed for cyclic structures. Using it on
  acyclic DFAs results in memory and time penalties but should not
  disrupt the processing beyond that. On a acyclic structures, a
  \verb+dfirst_cursor+ is more appropriated.
\end{itemize}
\paragraph{See Also \\}
depth-first cursor, stack cursor, \verb+dfirst_cursor+.

%%%%%%%%%%%%%%%%%%%%%%%%%% BFIRST_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf bfirst\_cursor$<$QueueCursor$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+bfirst_cursor+ implements the breadth-first traversal on acyclic
deterministic automata. It is an iterator on a sequence of transitions
ordered according to the breadth-first traversal algorithm. The method
\verb+next_transition+ 
allows to increment the cursor, making it point to the next transition
in the sequence. This methods returns \verb+true+ if the transition
reached has been enqueued and \verb+false+
otherwise (dequeue). \\
The \verb+bfirst_cursor+ is used in the same way as the iterators on
sequence to define ranges for algorithms. 
\paragraph{Example}
\begin{verbatim}
string w[4] = { "forward", "cursor", "code", "example" };
DFA_bin a;
tree_build(a, w, w + 4);
bfirst_cursor<queue_cursor<forward_cursor<DFA_bin<> > > >
  first = bfirstc(a), last;
while (first != last) {
  do 
    cout << "src " << first.src() << " letter " << first.letter()
         << " aim " << first.aim() << endl;
  while (first.next_transition());
}
\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|l|p{5cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+QueueCursor+ & the type of the underlying queue cursor & \\ \hline
\end{tabular}
\paragraph{Model of \\}
breadth-first cursor.
\paragraph{Type requirements}
\begin{itemize}
\item \verb+QueueCursor+ is a model of queue cursor.
\end{itemize}
\paragraph{Public base classes \\}
\verb+bfirst_cursor_concept+.
\paragraph{Members \\ [1ex]}
\begin{longtable}{|p{5.5cm}|p{1.7cm}|p{6.5cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{bfirst_cursor}
\end{longtable}
\paragraph{New Members \\ [1ex]}
\begin{tabular}{|l|p{7cm}|} \hline
\bf Member & \bf Description \\ \hline
\verb+bfirst_cursor(const QueueCursor &c)+ & Construct a cursor with
\verb+c+ as queue. \\ \hline
\end{tabular}
\paragraph{Helper Functions \\}
The function \verb+bfirst_c+ returns a \verb+bfirst_cursor+ constructed
from the object passed as argument. This object is allowed to be a
model of DFA, forward cursor or queue cursor.
\paragraph{Notes}
\begin{itemize}
\item Calls to method other than \verb+operator==+ are valid iff the cursor
queue is non-empty.
\item This cursor works only on acyclic structures, use
  \verb+bfirst_mark_cursor+ on cyclic DFAs.
\end{itemize}
\paragraph{See Also \\}
breadth-first cursor, queue cursor, \verb+bfirst_mark_cursor+.
\subsection{Cursor Adapters}
\subsection{Algorithms}
%%%%%%%%%%%%%%%%%%%%%%%%%%%% CCOPY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf ccopy}} \\
\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 DFirstCursor, class DFA>
DFA::state_type 
ccopy(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor());
\end{verbatim}
\paragraph{Description \\}
Copies the source automaton defined by the range \verb+[first, last)+
into the destination automaton \verb+out+ by performing a depth-first
traversal during which only the paths leading to final states are
copied : this algorithm trims uneeded states and transitions. On the
other hand, it only works on acyclic DFAs. See \verb+clone+ for cyclic
structures copy. \\
\verb+ccopy+ returns the first state of the iteration (the last
duplicated state).
\paragraph{Definition \\}
\verb+ccopy.h+
\paragraph{Requirements on types}
\begin{itemize}
\item \verb+DFirstCursor+ is a model of depth-first cursor.
\item \verb+DFA+ is a model of DFA.
\item \verb+DFirstCursor::char_type+ is convertible to
  \verb+DFA::char_type+. 
\end{itemize}
\paragraph{Preconditions}
\begin{itemize}
\item \verb+[first, last)+ is a valid range.
\item The source DFA is acyclic.
\end{itemize}
\paragraph{Complexity \\}
Linear: at most \verb+last - first+ transitions are duplicated.
\paragraph{Example}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <cursor.h>
#include <ccopy.h>
#include <set_operation.h>
#include <stream.h>
#include <iostream>