Inferno  0.2
walk.cpp
Go to the documentation of this file.
00001 
00002 #include "walk.hpp"
00003 #include "transformation.hpp"
00004 
00005 
00006 ////////////////////////// FlattenNode //////////////////////////
00007 
00008 bool FlattenNode_iterator::IsAtEnd() const
00009 {
00010     return empty || mit == m_end;
00011 }
00012 
00013 void FlattenNode_iterator::NormaliseNewMember()
00014 {
00015   if( !IsAtEnd() )
00016     if( ContainerInterface *con = dynamic_cast<ContainerInterface *>(GetCurrentMember()) )
00017     {
00018       cit = con->begin();
00019       c_end = con->end();
00020       BypassEndOfContainer();
00021     }
00022 }
00023 
00024 void FlattenNode_iterator::BypassEndOfContainer()
00025 {
00026   ASSERT( !IsAtEnd() && dynamic_cast<ContainerInterface *>(GetCurrentMember()) ); // this fn requires us to be on a container
00027   if( cit == c_end )
00028   {
00029     ++mit;
00030     NormaliseNewMember();
00031   }
00032 }
00033 
00034 FlattenNode_iterator::FlattenNode_iterator( TreePtr<Node> r ) :
00035   root( r ),
00036   empty( false )
00037 {
00038     //members = shared_ptr< vector< int > >( new vector< int >( root->BasicItemise() ) );
00039 
00040     mit = 0;
00041     m_end = root->ItemiseSize();
00042     NormaliseNewMember();
00043 }
00044 
00045 FlattenNode_iterator::FlattenNode_iterator() :
00046   empty( true )
00047 {
00048 }
00049 
00050 FlattenNode_iterator::FlattenNode_iterator( const FlattenNode_iterator & other ) :
00051     mit( other.mit ),
00052     m_end( other.m_end ),
00053     cit( other.cit ),
00054     c_end( other.c_end ),
00055     root( other.root ),
00056   empty( other.empty )
00057 {
00058 }
00059 
00060 FlattenNode_iterator::operator string() const
00061 {
00062     if (IsAtEnd())
00063       return string("end");
00064     else if( dynamic_cast<CollectionInterface *>(GetCurrentMember()) )
00065         return string("{") + TypeInfo(cit->get()).name() + string("}");
00066   else if( dynamic_cast<SequenceInterface *>(GetCurrentMember()) )
00067         return string("[") + TypeInfo(cit->get()).name() + string("]");
00068     else if( TreePtrInterface *ptr = dynamic_cast<TreePtrInterface *>(GetCurrentMember()) )
00069         return TypeInfo(*(ptr->get())).name();
00070     else
00071         ASSERTFAIL("got something from itemise that isn't a container or a shared pointer");
00072 }
00073 
00074 shared_ptr<ContainerInterface::iterator_interface> FlattenNode_iterator::Clone() const
00075 {
00076   shared_ptr<FlattenNode_iterator> ni( new FlattenNode_iterator(*this) );
00077   return ni;
00078 }
00079 
00080 FlattenNode_iterator &FlattenNode_iterator::operator++()
00081 {
00082   ASSERT( !IsAtEnd() );
00083     if( dynamic_cast<ContainerInterface *>(GetCurrentMember()) )
00084     {
00085       ++cit;
00086       BypassEndOfContainer();
00087     }
00088     else if( dynamic_cast<TreePtrInterface *>(GetCurrentMember()) )
00089     {
00090         ++mit;
00091         NormaliseNewMember();
00092     }
00093     else
00094     {
00095         ASSERTFAIL("got something from itemise that isn't a container or a shared pointer");
00096     }
00097   return *this;
00098 }
00099 
00100 FlattenNode_iterator::reference FlattenNode_iterator::operator*() const
00101 {
00102     ASSERT( !IsAtEnd() );
00103   if( dynamic_cast<ContainerInterface *>(GetCurrentMember()) )
00104         return *cit;
00105     else if( TreePtrInterface *ptr = dynamic_cast<TreePtrInterface *>(GetCurrentMember()) )
00106         return *ptr;
00107     else
00108         ASSERTFAIL("got something from itemise that isn't a container or a shared pointer");
00109 }
00110 
00111 FlattenNode_iterator::pointer FlattenNode_iterator::operator->() const
00112 {
00113   return &operator*();
00114 }
00115 
00116 bool FlattenNode_iterator::operator==( const ContainerInterface::iterator_interface &ib ) const
00117 {
00118   const FlattenNode_iterator *pi = dynamic_cast<const FlattenNode_iterator *>(&ib);
00119   ASSERT(pi)("Comparing traversing iterator with something else ")(ib);
00120   if( pi->IsAtEnd() || IsAtEnd() )
00121     return pi->IsAtEnd() && IsAtEnd();
00122   return *pi == *this; 
00123 }
00124 
00125 void FlattenNode_iterator::Overwrite( FlattenNode_iterator::pointer v ) const
00126 {
00127     ASSERT( !IsAtEnd() );
00128   if( dynamic_cast<ContainerInterface *>(GetCurrentMember()) )
00129         cit.Overwrite( v );
00130     else if( TreePtrInterface *ptr = dynamic_cast<TreePtrInterface *>(GetCurrentMember()) )
00131         *ptr = *v;
00132     else
00133         ASSERTFAIL("got something from itemise that isn't a container or a shared pointer");
00134 }
00135 
00136 const bool FlattenNode_iterator::IsOrdered() const
00137 {
00138   return true; // traverse walks tree in order generally
00139 }
00140 
00141 
00142 ////////////////////////// Walk //////////////////////////
00143 
00144 bool Walk_iterator::IsAtEndOfChildren() const
00145 {
00146   ASSERT( !done );
00147 
00148   if( state.empty() )
00149     return false;
00150 
00151     return state.top().iterator == state.top().container->end();
00152 }
00153 
00154 void Walk_iterator::BypassEndOfChildren()
00155 {
00156   ASSERT( !done );
00157   while( IsAtEndOfChildren() )
00158   {
00159     state.pop();
00160 
00161       done = state.empty();
00162       if( done )
00163         break;
00164 
00165       ++state.top().iterator;
00166   }
00167 }
00168 
00169 shared_ptr<ContainerInterface> Walk_iterator::GetChildContainer( TreePtr<Node> n ) const
00170 { 
00171     return shared_ptr<ContainerInterface>( new FlattenNode(n) );
00172 }        
00173 
00174 void Walk_iterator::Push( TreePtr<Node> n )
00175 { 
00176     StateEntry ns;
00177     ns.container = GetChildContainer( n );
00178     ns.iterator = ns.container->begin();
00179     state.push( ns );
00180 }        
00181 
00182 Walk_iterator::Walk_iterator( TreePtr<Node> &r,
00183                               Filter *of,
00184                                   Filter *rf ) :
00185     root( new TreePtr<Node>(r) ),
00186     out_filter( of ),
00187     recurse_filter( rf ),
00188     done( false )
00189 {
00190     DoNodeFilter();
00191 }
00192 
00193 Walk_iterator::Walk_iterator() :
00194     out_filter( NULL ),
00195     recurse_filter( NULL ),
00196     done( true )
00197 {
00198 }        
00199 
00200 Walk_iterator::Walk_iterator( const Walk_iterator & other ) :
00201   root( other.root ),
00202     out_filter( other.out_filter ),
00203     recurse_filter( other.recurse_filter ),
00204   state( other.state ),
00205   done( other.done )
00206 {
00207 }
00208 
00209 Walk_iterator::operator string() const
00210 {
00211     string s;
00212     stack< StateEntry > ps = state; // std::stack doesn't have [] so copy the whole thing and go backwards
00213     while( !ps.empty() )
00214     {
00215         s = string(*(ps.top().iterator)) + string(" ") + s;
00216         ps.pop();
00217     }
00218     return s;
00219 }
00220 
00221 void Walk_iterator::AdvanceInto()
00222 {
00223   ASSERT( !done );
00224   ASSERT( !IsAtEndOfChildren() );
00225   TreePtr<Node> element = **this; // look at current node
00226   bool recurse = false;
00227   if( element ) // must be non-NULL
00228   {
00229     recurse = true;
00230     if( recurse_filter ) // is there a filter on recursion?
00231     {
00232             //TRACE("Recurse filter @%p, this@%p, entering...\n", recurse_filter, this);
00233       bool ok = recurse_filter->IsMatch( element, element ); // must pass the restriction
00234       //TRACE("Recurse filter @%p, leaving...\n", recurse_filter);
00235 
00236       if( !ok )
00237         recurse = false;
00238     }
00239     //else
00240             //TRACE("No recurse filter\n", recurse_filter);
00241   }
00242 
00243     if( recurse )
00244     {
00245       // Step into
00246         Push( **this );
00247         BypassEndOfChildren();
00248     }
00249     else
00250     {
00251       // If we can't step into then step over
00252       AdvanceOver();
00253     }
00254 }
00255 
00256 void Walk_iterator::AdvanceOver()
00257 {
00258   ASSERT( !done );
00259   ASSERT( !IsAtEndOfChildren() );
00260 
00261   if( state.empty() )
00262   {
00263     // At top level there's only one element, so finish the walk
00264     done = true;
00265   }
00266   else
00267   {
00268     // otherwise, propagate
00269       ++state.top().iterator;
00270         BypassEndOfChildren();
00271   }
00272 }
00273 
00274 shared_ptr<ContainerInterface::iterator_interface> Walk_iterator::Clone() const
00275 {
00276   shared_ptr<Walk_iterator> ni( new Walk_iterator(*this) );
00277   return ni;
00278 }
00279 
00280 Walk_iterator &Walk_iterator::operator++()
00281 {
00282   AdvanceInto();
00283     DoNodeFilter();
00284   return *this;
00285 }
00286 
00287 Walk_iterator::reference Walk_iterator::operator*() const
00288 {
00289     ASSERT( !done )("Already advanced over everything; reached end of walk");
00290     ASSERT( !IsAtEndOfChildren() );
00291 
00292   if( state.empty() )
00293   {
00294     return *root;
00295   }
00296   else
00297   {
00298         return *(state.top().iterator);
00299   }
00300 }
00301 
00302 Walk_iterator::pointer Walk_iterator::operator->() const
00303 {
00304   return &operator*();
00305 }
00306 
00307 bool Walk_iterator::operator==( const ContainerInterface::iterator_interface &ib ) const
00308 {
00309   const Walk_iterator *pi = dynamic_cast<const Walk_iterator *>(&ib);
00310   ASSERT(pi)("Comparing walking iterator with something else ")(ib);
00311   if( pi->done || done )
00312     return pi->done && done;
00313   return **pi == **this;
00314 }
00315 
00316 void Walk_iterator::Overwrite( Walk_iterator::pointer v ) const
00317 {
00318     ASSERT( !done )("Already advanced over everything; reached end of walk");
00319     ASSERT( !IsAtEndOfChildren() );
00320 
00321     if( state.empty() )
00322     {
00323       *root = *v;
00324     }
00325     else
00326     {
00327         state.top().iterator.Overwrite( v );
00328     }
00329 }
00330 
00331 const bool Walk_iterator::IsOrdered() const
00332 {
00333   return true; // walk walks tree in order generally
00334 }
00335 
00336 void Walk_iterator::DoNodeFilter()
00337 {
00338     while(!done)
00339     {
00340         TreePtr<Node> element = **this; // look at current node
00341         
00342         // TODO pass NULLs to filter, let it decide what to do
00343         bool ok = true;
00344         if( out_filter )
00345             if( !element || !out_filter->IsMatch( element) ) 
00346                 ok = false;
00347          
00348         if( ok )
00349         {
00350             return;
00351         }
00352         
00353         AdvanceInto();
00354     }    
00355 }
00356 
00357 ////////////////////////// UniqueFilter //////////////////////////
00358 
00359 bool UniqueFilter::IsMatch( TreePtr<Node> context,
00360                             TreePtr<Node> root )
00361 {
00362     ASSERT( root );
00363     (void)context;
00364     
00365     //TRACE("Got ")(*root)("\n");
00366     
00367     if( seen.IsExist( root ) )
00368         return false;
00369     
00370     seen.insert( root );
00371     return true;        
00372 }
00373 
00374 ////////////////////////// ParentWalk //////////////////////////
00375 
00376 ParentWalk_iterator::ParentWalk_iterator() :
00377     unique_filter( new UniqueFilter )
00378 {
00379 }        
00380 
00381 ParentWalk_iterator::~ParentWalk_iterator() 
00382 {
00383     delete unique_filter;
00384 }        
00385 
00386 ParentWalk_iterator::ParentWalk_iterator( const ParentWalk_iterator & other ) :
00387     Walk_iterator( other )
00388 {
00389     unique_filter = new UniqueFilter( *(other.unique_filter) );
00390     recurse_filter = unique_filter; 
00391 }
00392 
00393 ParentWalk_iterator &ParentWalk_iterator::operator=( const ParentWalk_iterator & other )
00394 {
00395     Walk_iterator::operator=( other ),
00396     *unique_filter = *(other.unique_filter);
00397     recurse_filter = unique_filter; 
00398     return *this;
00399 }
00400 
00401 ParentWalk_iterator::ParentWalk_iterator( TreePtr<Node> &root ) :
00402     Walk_iterator( root, NULL, unique_filter = new UniqueFilter )
00403 {
00404 }
00405 
00406 shared_ptr<ContainerInterface::iterator_interface> ParentWalk_iterator::Clone() const
00407 {
00408   shared_ptr<ParentWalk_iterator> ni( new ParentWalk_iterator(*this) );
00409   return ni;
00410 }
00411 
00412 ////////////////////////// UniqueWalk //////////////////////////
00413 
00414 UniqueWalk_iterator::UniqueWalk_iterator() :
00415     unique_filter( new UniqueFilter )
00416 {
00417 }        
00418 
00419 UniqueWalk_iterator::~UniqueWalk_iterator()
00420 {
00421     delete unique_filter;
00422 }        
00423 
00424 UniqueWalk_iterator::UniqueWalk_iterator( const UniqueWalk_iterator & other ) :
00425     Walk_iterator( other )
00426 {
00427     unique_filter = new UniqueFilter( *(other.unique_filter) );
00428     out_filter = unique_filter; 
00429 }
00430 
00431 UniqueWalk_iterator &UniqueWalk_iterator::operator=( const UniqueWalk_iterator &other )
00432 {
00433     Walk_iterator::operator=( other );
00434     *unique_filter = *(other.unique_filter);
00435     out_filter = unique_filter; 
00436     return *this;
00437 }
00438 
00439 UniqueWalk_iterator::UniqueWalk_iterator( TreePtr<Node> &root ) :
00440     Walk_iterator( root, unique_filter = new UniqueFilter, NULL )
00441 {
00442 }
00443 
00444 shared_ptr<ContainerInterface::iterator_interface> UniqueWalk_iterator::Clone() const
00445 {
00446   shared_ptr<UniqueWalk_iterator> ni( new UniqueWalk_iterator(*this) );
00447   return ni;
00448 }
00449 
00450