package DFA::Set;

use strict;
use vars qw($VERSION @ISA);

use Carp;

$VERSION = '0.01';


#####################################################################
sub new
{
    my($package, %params)=@_;
    
    croak "Usage: new $package (States=>[...])"
            unless $params{States};

    if(ref $params{States} eq 'ARRAY') { # turn States into a hash for speed
        my $t=$params{States};
        $params{States}={};
        @{$params{States}}{@$t}={transition=>$t};
    }
    elsif(ref $params{States} ne 'HASH') {
        croak "States must be arrayref or hashref";
    }
    else {                         # turn list of transitions into hashref
        foreach my $s (keys %{$params{States}}) {
            my $t=$params{States}{$s};
            $params{States}{$s}={transition=>$t};
        }
    }

    # turn accceptable transitions into hashrefs
    foreach my $s (values %{$params{States}}) {
        my $t=$s->{transition};
        next if ref $t eq 'HASH';
        croak "State transition must be arrayref or hashref" 
                unless ref $t eq 'ARRAY';
        $s->{transition}={};
        @{$s->{transition}}{@$t}=(1) x @$t;
    }

    return bless {%params}, $package;
}

#####################################################################
sub add
{
    my($self, $name, $obj, $state)=@_;
    croak "Adding object to unknown state $state" 
                    unless exists $self->{States}{$state};
    # must be implemented
    return;
}

#####################################################################
sub remove
{
    my($self, $name)=@_;

    croak "Please overload ", ref($self), "->remove\n";
    return;
}

#####################################################################
sub find_state
{
    my($self, $name)=@_;
    croak "Please overload ", ref($self), "->find_state\n";
    return;
}

#####################################################################
sub find_payload
{
    my($self, $name)=@_;
    croak "Please overload ", ref($self), "->find_payload\n";
    return;
}

#####################################################################
sub list
{
    my($self, $state)=@_;
    croak "Listing objects in unknown state $state" 
                    unless exists $self->{States}{$state};
    return;
}

#####################################################################
sub transition
{
    my($self, $name, $newstate)=@_;
    my $state=$self->find_state($name);
    croak "Transitioning object to unknown state $state" 
                    unless exists $self->{States}{$newstate};
    croak "Illegal state transition $state -> $newstate"
        unless $self->{States}{$state}{transition}{$newstate};
    return ($self->{Terminal} and $self->{Terminal} eq $newstate);
}


1;
__END__
# Below is the stub of documentation for your module. You better edit it!

=head1 NAME

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

=head1 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");


=head1 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.

=head2 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.

=head2 DFA::Set::Memory

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

=head2 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).


=head1 METHODS

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

=head2 new

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

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

=over 8

=item 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 C<transition>
call.

=item Terminal

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

=back




=head2 add

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

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

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

=head2 remove

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

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

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



=head2 list

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

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

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

=head2 transition

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

Moves token C<$name> from it's current state to C<$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 C<$newstate> doesn't exist or
if C<$name> isn't in the DFA.  Implementations should call
$self->SUPER::transition to varify valid transitions.

Returns TRUE if $newstate is the Terminal.


=head2 find_state

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

Returns the state that the token C<$name> is in.  

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


=head2 find_payload

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

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


=head1 AUTHOR

Philip Gwyn <cpan at pied.nu>

=head1 SEE ALSO

DFA::Set::Memory, DFA::Set::File, perl(1).

=cut