Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <list>
- #include <vector>
- #include <string>
- //Excuse the weird kind of tree I use here. A struct Tree{ Tree *left, *right; };
- //would show the same problem with less code, but this is the kind of tree I need
- //so I might as well keep it.
- template< typename T, typename U >
- std::vector<T> & operator << ( std::vector<T> & v, const U & t ) {
- v.push_back( t );
- return v;
- }
- struct Tree {
- //match does what you'd expect == to do.
- virtual bool match( const Tree * ) const = 0;
- };
- struct Branch : Tree {
- std::vector< Tree * > branch;
- Branch( const std::vector< Tree * > & branch ) : branch( branch ) {}
- virtual bool match( const Tree * t ) const {
- const Branch * b = dynamic_cast< const Branch * > ( t );
- if( b == 0 || b->branch.size() != branch.size() ) return false;
- for( unsigned i = 0; i < branch.size(); i++ )
- if( ! branch[ i ]->match( b->branch[ i ] ) ) return false;
- return true;
- }
- };
- struct Leaf : Tree {
- std::string leaf;
- Leaf( const std::string & leaf ) : leaf( leaf ) {
- }
- virtual bool match( const Tree * t ) const {
- const Leaf * l = dynamic_cast< const Leaf * > ( t );
- return l != 0 && l->leaf == leaf;
- }
- };
- #define B std::vector< Tree * >()
- //the set of possible conversions
- std::vector< std::pair< Tree *, Tree * > > map;
- template< typename Container, typename Value, typename Matcher >
- bool find( Container where, Value what, Matcher match ) {
- for( Container::iterator it = where.begin(); it != where.end(); it++ )
- if( match( *it, what ) ) return true;
- return false;
- }
- bool exact_match( Tree * x, Tree * y ) {
- return x->match( y );
- }
- bool path( Tree *, Tree * );
- //Returns true if trees are identical, or can be converted from one to another
- //by converting their children.
- bool short_path( Tree * x, Tree * y ) {
- if( x->match( y ) ) return true;
- else{
- Branch * a = dynamic_cast< Branch * > ( x );
- Branch * b = dynamic_cast< Branch * > ( y );
- if( a != 0 && b != 0 && a->branch.size() == b->branch.size() ) {
- for( unsigned i = 0; i < a->branch.size(); i++ )
- if( !path( a->branch[i], b->branch[i] ) ) return false;
- return true;
- }
- }
- return false;
- }
- //The main function. Just the usual pathfinding. No backtracking partly
- //to make it cleaner and partly because it's a pain to write.
- //The function works fine in simple cases.
- bool path( Tree * x, Tree * y ) {
- std::list< Tree * > open, close;
- open.push_back( x );
- while( !open.empty() && !short_path( open.front(), y ) ) {
- for( unsigned i = 0; i < map.size(); i++ ) {
- if( short_path( open.front(), map[i].first ) && !find( open, map[i].second, exact_match ) && !find( close, map[i].second, exact_match ) )
- open.push_back( map[i].second );
- }
- close.push_back( open.front() );
- open.pop_front();
- }
- return !open.empty();
- }
- int main(){
- //The same example I gave in my post.
- map.push_back( std::pair<Tree*, Tree*>( new Leaf( "A" ), new Branch( B << new Leaf( "A" ) << new Leaf( "A" ) ) ) );
- map.push_back( std::pair<Tree*, Tree*>( new Branch( B << new Leaf( "A" ) << new Leaf( "A" ) ), new Leaf( "C" ) ) );
- map.push_back( std::pair<Tree*, Tree*>( new Leaf( "C" ), new Branch( B << new Leaf( "B" ) << new Leaf( "B" ) ) ) );
- map.push_back( std::pair<Tree*, Tree*>( new Branch( B << new Leaf( "B" ) << new Leaf( "B" ) ), new Leaf( "B" ) ) );
- bool test = path( new Leaf( "A" ), new Leaf( "B" ) );
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment