NAME

DFA::Set - Virtual base class for a Deterministic Finite Automata

SYNOPSIS

    use DFA::Set::Memory;       # note : one doen't use DFA::Set directly
    
    $dfa=DFA::Set::Memory->new(
        States=>{
            Foo=>[qw(Biff)],
            Biff=>[qw(Foo Bob)],
            Bob=>[],
        }, 
        Terminal=>'Bob');

    $dfa->add("bob", $bob, "Foo");
    $dfa->add("bill", $bill, "Foo");

    $dfa->transition(bob=>'Biff');
    if($dfa->transition(bob=>'Bob')) {
        $dfa->remove('bob');
    }

    $obill=$dfa->find_payload("bill");

DESCRIPTION

A Deterministic Finite Automata is a state machine where all conditions are known before hand (hence is deterministic). DFA::Set is a virtual base class that you will overload to add various features to your DFA. It is designed with the idea that several tokens or objects will be present in the DFA at a given time. Transitions (ie, moving a token from one state to another) are the *callers* responsibility. DFA::Set will check to make sure that transitions meet the constraints that were given at instantiation time.

Tokens within the DFA are represented by a unique name and have a payload attached to them. The payload can be a reference or just a scalar, depending on the implementation. This means that DFA::Set also acts as a sort-of data store, which could be construed as being at odds with it's minimalist phylosophy. Bite me.

IMPLEMENTATIONS

As you might have noticed, DFA::Set is in fact a virtual base class. This means that you won't be using it directly, but rather using a class that inherits from it. Here are 2 that are included with this distro.

DFA::Set::Memory

This is a basic implentation that uses hashes in memory to store information and objects.

DFA::Set::File

This is another implementation that uses files and directories to make sure that transitions are atomic. This has the advantage of never being able to loose information if the program crashes unexpectedly (unless the filesystem crashes also, in which case there's not much one can do).

METHODS

The following methods should be overloaded to implement various features to for the set.

new

    my $dfa=new DFA::Set (%params);

Creates and initialises a new DFA. %params has the following keys :

States

Defines all the states in the DFA. Can be a hashref or arrayref. If it is an arrayref, each element is a scalar state name and tokens can transition from any state to any other state. If it is a hashref, the keys are state names, and the values are the arrayrefs of states that a token can transition too. This is harder to explain then it really is.

Cannonical case, Maildir example :

    States=>{
        tmp=>['new'],
        new=>['cur'],
        cur=>[],
    },

This means that tokens can go from tmp -> new -> cur, but no other transition is possible.

Fast typing :

    States=>[qw(tmp new cur)],

This means that tokens can go from any state to any other state. IE tmp -> cur -> new -> tmp -> cur and so on. (This is illegal for Maildirs.) Included for cases where you want to impose limits above the transition call.

Terminal

Defines the terminal state. This does nothing much right now (see transition) but is included for completeness.

add

    $dfa->add($name, $payload, $state);

Adds a token to the DFA, putting it in state $state. The token is named $name and can carry a $payload with it (see find_payload below). $name MUST be unique in the DFA. Enforcing a unique name is left as an exercise to the caller. Possible data types for $payload depends on how the DFA::Set implementation.

Croaks if $state isn't valid in the DFA.

remove

    $dfa->remove($name[, $state]);

Removes a token named $name from the DFA. Some DFA::Set implementations allow you to also specify $state to speed up operation.

Will croak if $name isn't in the DFA.

list

    @names=$dfa->list($state);

Returns a list of all the tokens in $state. This can be useful for setting up batch jobs, or for debuging purposes.

Will croak if $state isn't defined in the DFA.

transition

    $dfa->transition($name, $newstate);

Moves token $name from it's current state to $newstate. Contrary to most DFAs no callbacks are called on the transition. This is because DFA::Set is an data representation of the DFA, not a DFA processor.

Will croak if this is an illeagal transition, if $newstate doesn't exist or if $name isn't in the DFA. Implementations should call $self->SUPER::transition to varify valid transitions.

Returns TRUE if $newstate is the Terminal.

find_state

    my $state=$dfa->find_state($name);

Returns the state that the token $name is in.

Will croak if $name isn't in the DFA.

find_payload

    my $payload=$dfa->find_payload($name[, $state]);

Returns the payload of token $name. Some DFA::Set implementations allow you to also specify $state to speed up operation.

AUTHOR

Philip Gwyn <cpan at pied.nu>