previousnext
ASTL homeSTL home
DFA_mtf


Implements

DFA

Class Specifications

name DFA_mtf
template parameters class _Sigma = Type_alphabet<char>,
class _Tag = empty_tag,
class Allocator = default_allocator
constructor DFA_mtf(unsigned long = 0, Allocator a = Allocator())

File

dfa_mtf.h

Structure

This is one of the three arrays DFA. In thes representation, we store the outgoing transitions of a state in an array of couples in Sigma*Q. they are to be used when space memory constraints are strong since they are the least consumming structures.
Each state is a pair of tag and STL vector storing couples in Sigma*Q. Here the transitions are kept unordered and looking up takes linear time. to speed up the process, once found, the wanted transition is placed at the beginning of the array and the others are shifted back so that, after a number of accesses, the most popular transitions find themselves up-front. F is a bit vector.

time

Add/remove state: O(1)
Add transition: amortized O(1)
Remove transition: O(c)
Access transition: +/-O(c)
Iteration on edges: O(c)

Space

Use Cases

Again, this class is usefull when memory is limited. Transition access may be slower than for the DFA_bin but adding a transition takes amortized constant time (due to insertion at the back of a STL vector) whereas adding a transition to a DFA_bin takes linear time