[boost] Proposal: cartesian_product algorithm and a finite state machinetemplate library

From: Marc Jacobs (marcja_at_[hidden])
Date: 2002-10-29 13:46:36

I'd like to offer two submissions to Boost.

----------------------------
The first is a straightforward implementation of a cartesian product on two
ranges. That is, given iterators on two ranges, perform a binary operation
on every combination of elements. Here is a pseudo-code example:

r1 = { 'A', 'B', 'C' }
r2 = { 'D', 'E', 'F' }
// concat() is a binary functor that concatenates two characters into a
string
cartesian_product( r1.begin(), r1.end(), r2.begin(), r2.end(), concat() )
// returns
// 'AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF'

I've used this algorithm while implementing a makefile-ish file parser.
Given a file such as:

one two : three four five
six : seven

where tokens to the left of the colon on a single line depend on all the
tokens on the right of the colon on the same line, generate all pairs of
dependencies, e.g. "one : three", "one : four", "two : three", etc.

----------------------------
The second proposal is for a finite state machine template library. Using a
mix of generic and object-oriented programming paradigms, it provides a
simple basis for declaring and running relatively non-invasive finite state
machines on application classes without resorting to code-generation tools
such as AutoFSM.

Example usage (which could be simplified using judicious of template and/or
preprocessor metaprogramming) looks like:

class ApplicationClass { ... };

namespace fsm {
    namespace states {
        enum {
            off,
            on
        }
    }

    namespace events {
        enum {
            powerup,
            powerdown
        }
    }

    class polystate {
    public:
        virtual void transition( fsmtl::event< events::powerup > ) {
default_handler(); }
        virtual void transition( fsmtl::event< events::powerdown > ) {
default_handler(); }
    protected:
        virtual void default_handler() { throw fsmtl::bad_transition(); }
    }

    typedef fsmtl::machine< ApplicationClass, polystate > context;
}

namespace fsmtl
{
    using fsm::states;
    using fsm::events;
    using fsm::context;

    typedef fsm::polystate polystate;

    template<>
    struct state< states::off, polystate > : public polystate {
        virtual void transition( event< events::powerup > ) {
            context::alter( select_state< states::on >() );
        }
    };

    template<>
    struct state< states::on, polystate > : public polystate {
        virtual void transition( event< events::powerdown > ) {
            context::alter( select_state< states::off >() );
        }
    };
}

// fsm::context::raise( select_event< events::powerup >() );

// fsm::context::raise( select_event< events::powerdown >() );

Marc Jacobs