dfirst_cursor Class Template Reference

Implements the depth-first traversal on deterministic automata. More...

#include <cursor.h>

Inherits astl::dfirst_cursor_concept.

List of all members.

Public Types

typedef StackCursor::char_traits char_traits
 Character traits describing char_type.
typedef StackCursor::char_type char_type
 The type of the transitions letters.
typedef StackCursor::state_type state_type
 The type of the automaton-states identifiers.
typedef StackCursor::tag_type tag_type
 The type of the data attached to states.

Public Member Functions

state_type aim () const
 Returns the aim state of the pointed transition.
bool aim_final () const
 Returns true if the aim state of the transition that this cursor points to is final.
tag_type aim_tag () const
 Returns the data attached to the aim state of the pointed transition.
void backward ()
 Forces the cursor to act as if there was no more transitions to push.
 dfirst_cursor ()
 Creates a cursor with an empty stack used as an end-of-range iterator.
 dfirst_cursor (const StackCursor &x, const MarkerFunction &f=MarkerFunction())
 Creates a cursor with x as stack.
bool forward ()
 Increments the cursor making it point to the next transition in the sequence.
char_type letter () const
 Returns the letter on the pointed transition.
bool operator!= (const self &x) const
 Returns true if stacks are different.
bool operator== (const self &x) const
 Returns true if both stacks are equal.
state_type src () const
 Returns the identifier of the state that this cursor points to.
bool src_final () const
 Returns true if the state that this cursor points to is final.
tag_type src_tag () const
 Returns the data attached to the state that this cursor points to.
const StackCursor & stack () const
 Returns the stack container.


Detailed Description

template<typename StackCursor, typename MarkerFunction = none>
class astl::dfirst_cursor< StackCursor, MarkerFunction >

Implements the depth-first traversal on deterministic automata.

It is in some sense an iterator on a sequence of transitions ordered according to the depth-first traversal algorithm. The method forward allows to increment the cursor, making it point to the next transition in the sequence. This methods returns true if the transition reached has been pushed onto the stack (forward move) and false otherwise (pop and backward move).

The dfirst_cursor is fundamental because it is used much in the same way as the iterators on sequence to define ranges for algorithms.

Template parameters
ParameterDescriptionDefaultRequirements
StackCursor The type of the stack cursorStackCursor is a model of stack cursor
MarkerFunction The type of state marker used for preventing the cursor from visiting twice the same transition on cyclic automata and DAGsnone MarkerFunction is either none, set_marker<ForwardCursor::state_type> or a model of state marker
Model of
dfirst_cursor
Associated Helper Functions
dfirstc(), dfirst_markc()

Member Function Documentation

state_type aim (  )  const

Returns the aim state of the pointed transition.

Precondition:
The stack is not empty

bool aim_final (  )  const

Returns true if the aim state of the transition that this cursor points to is final.

Precondition:
The stack is not empty

tag_type aim_tag (  )  const

Returns the data attached to the aim state of the pointed transition.

Precondition:
The stack is not empty

bool forward (  ) 

Increments the cursor making it point to the next transition in the sequence.

Returns true if the transition reached has been pushed on the stack.

Precondition:
The stack is not empty

char_type letter (  )  const

Returns the letter on the pointed transition.

Precondition:
The stack is not empty

state_type src (  )  const

Returns the identifier of the state that this cursor points to.

Precondition:
The stack is not empty

bool src_final (  )  const

Returns true if the state that this cursor points to is final.

Precondition:
The stack is not empty

tag_type src_tag (  )  const

Returns the data attached to the state that this cursor points to.

Precondition:
The stack is not empty


Generated on Sun Mar 8 02:41:36 2009 for ASTL by  doxygen 1.5.7.1