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