Guest User

Untitled

a guest
Jun 28th, 2011
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None | 0 0
  1. #include <list>
  2. #include <vector>
  3. #include <string>
  4.  
  5. //Excuse the weird kind of tree I use here. A struct Tree{ Tree *left, *right; };
  6. //would show the same problem with less code, but this is the kind of tree I need
  7. //so I might as well keep it.
  8.  
  9. template< typename T, typename U >
  10. std::vector<T> & operator << ( std::vector<T> & v, const U & t ) {
  11.    v.push_back( t );
  12.    return v;
  13. }
  14.  
  15. struct Tree {
  16.    //match does what you'd expect == to do.
  17.    virtual bool match( const Tree * ) const = 0;
  18. };
  19.  
  20. struct Branch : Tree {
  21.    std::vector< Tree * > branch;
  22.  
  23.    Branch( const std::vector< Tree * > & branch ) : branch( branch ) {}
  24.  
  25.    virtual bool match( const Tree * t ) const {
  26.       const Branch * b = dynamic_cast< const Branch * > ( t );
  27.       if( b == 0 || b->branch.size() != branch.size() ) return false;
  28.  
  29.       for( unsigned i = 0; i < branch.size(); i++ )
  30.          if( ! branch[ i ]->match( b->branch[ i ] ) ) return false;
  31.  
  32.       return true;
  33.    }
  34. };
  35.  
  36. struct Leaf : Tree {
  37.    std::string leaf;
  38.  
  39.    Leaf( const std::string & leaf ) : leaf( leaf ) {
  40.    }
  41.  
  42.    virtual bool match( const Tree * t ) const {
  43.       const Leaf * l = dynamic_cast< const Leaf * > ( t );
  44.       return l != 0 && l->leaf == leaf;
  45.    }
  46. };
  47.  
  48. #define B std::vector< Tree * >()
  49.  
  50. //the set of possible conversions
  51. std::vector< std::pair< Tree *, Tree * > > map;
  52.  
  53. template< typename Container, typename Value, typename Matcher >
  54. bool find( Container where, Value what, Matcher match ) {
  55.    for( Container::iterator it = where.begin(); it != where.end(); it++ )
  56.       if( match( *it, what ) ) return true;
  57.    return false;
  58. }
  59.  
  60. bool exact_match( Tree * x, Tree * y ) {
  61.    return x->match( y );
  62. }
  63.  
  64. bool path( Tree *, Tree * );
  65.  
  66. //Returns true if trees are identical, or can be converted from one to another
  67. //by converting their children.
  68. bool short_path( Tree * x, Tree * y ) {
  69.  
  70.    if( x->match( y ) ) return true;
  71.    else{
  72.  
  73.       Branch * a = dynamic_cast< Branch * > ( x );
  74.       Branch * b = dynamic_cast< Branch * > ( y );
  75.  
  76.       if( a != 0 && b != 0 && a->branch.size() == b->branch.size() ) {
  77.  
  78.          for( unsigned i = 0; i < a->branch.size(); i++ )
  79.             if( !path( a->branch[i], b->branch[i] ) ) return false;
  80.  
  81.          return true;
  82.  
  83.       }
  84.    }
  85.    return false;
  86. }
  87.  
  88. //The main function. Just the usual pathfinding. No backtracking partly
  89. //to make it cleaner and partly because it's a pain to write.
  90. //The function works fine in simple cases.
  91. bool path( Tree * x, Tree * y ) {
  92.    std::list< Tree * > open, close;
  93.    open.push_back( x );
  94.  
  95.    while( !open.empty() && !short_path( open.front(), y ) ) {
  96.  
  97.       for( unsigned i = 0; i < map.size(); i++ ) {
  98.  
  99.          if( short_path( open.front(), map[i].first ) && !find( open, map[i].second, exact_match ) && !find( close, map[i].second, exact_match ) )
  100.             open.push_back( map[i].second );
  101.  
  102.       }
  103.  
  104.       close.push_back( open.front() );
  105.       open.pop_front();
  106.  
  107.    }
  108.  
  109.    return !open.empty();
  110. }
  111.  
  112. int main(){
  113.    //The same example I gave in my post.
  114.    map.push_back( std::pair<Tree*, Tree*>( new Leaf( "A" ), new Branch( B << new Leaf( "A" ) << new Leaf( "A" ) ) ) );
  115.    map.push_back( std::pair<Tree*, Tree*>( new Branch( B << new Leaf( "A" ) << new Leaf( "A" ) ), new Leaf( "C" ) ) );
  116.    map.push_back( std::pair<Tree*, Tree*>( new Leaf( "C" ), new Branch( B << new Leaf( "B" ) << new Leaf( "B" ) ) ) );
  117.    map.push_back( std::pair<Tree*, Tree*>( new Branch( B << new Leaf( "B" ) << new Leaf( "B" ) ), new Leaf( "B" ) ) );
  118.    bool test = path( new Leaf( "A" ), new Leaf( "B" ) );
  119.    return 0;
  120. };
Advertisement
Add Comment
Please, Sign In to add comment