NFD

Task #1318

Updated by Junxiao Shi almost 12 years ago

Implement the new API for NameTree enumeration functions. 

 ## API 

     namespace name_tree { 
     /// determines whether to visit an entry 
     typedef function<bool(const Entry&)> EntrySelector; 
     /// a functor that accepts any entry 
     class AnyEntry : public EntrySelector; 
     /// determines whether to an entry and/or its descendants 
     /// \return .first indicates whether to visit entry, .second indicates whether to visit its descendants 
     typedef function<std::pair<bool,bool>(const Entry&)> name_tree::Entry&)> EntrySubtreeSelector; 
     /// a functor that accepts any entry and its descendants 
     class AnyEntrySubtree : public EntrySubtreeSelector; 
     } // namespace name_tree 
    
     partial class NameTree 
     { 
       /// ForwardIterator; *it is name_tree::Entry& type 
       typedef ... const_iterator; 
       /// full enumerate 
       const_iterator fullEnumerate(const EntrySelector& selector = AnyEntry()) const; 
       /// partial enumerate; an entry is included if accepted by selector, and none of its ancestors is rejected by subTreeSelector 
       const_iterator partialEnumerate(const Name& name, const EntrySubtreeSelector& selector = AnyEntrySubtree()) const; 
       /// enumerate along name and name's ancestors 
       const_iterator findAllMatches(const Name& name, const EntrySelector& selector = AnyEntry()) const; 
       /// begin iterator (full enumerate) 
       const_iterator begin() const; 
       /// end iterator 
       const_iterator end() const; 
     }; 

 Notes: 

 * The snippet assumes using STL iterators. It's equally fine to use [Boost.Range](http://www.boost.org/doc/libs/1_48_0/libs/range/doc/html/index.html). 
 * The snippet assumes all three operations use the same type of iterator. It's equally fine to have different types.   
   If different iterator types are used, `fullEnumerate` `partialEnumerate` `findAllMatches` should return `std::pair<const_iterator, const_iterator>`, and `begin` `end` are unnecessary. 
 * It's unacceptable to create a new container and copy results into it. 

 ## Examples 

 Give a NameTree containing these entries: 

 * / 
 * /A 
 * /A/B 
 * /A/B/C 
 * /A/D 
 * /E 
 * /F 

 **.fullEnumerate**(f) ~ .end(), where f accepts A,C,E,F only:   
 visits A,C,E,F in any order. 

 **.partialEnumerate**(/A, f) ~ .end(), where f accepts root,B,C,D entries and root,A,F subtrees only:   
 visits B,D in any order.   
 If an entry is rejected, its children can still be visited (eg. A is rejected, but B can be visited).   
 If a subtree is rejected, its children are skipped, but the root entry of subtree can be visited (eg. B is rejected, so C is skipped, but B is visited). 

 **.findAllMatches**(/A/B/C/D, f) ~ .end(), where f accepts root,B,C,F only:   
 visits root,B,C in any order. 

 **.begin**() ~ .end():   
 equivalent to .fullEnumerate(AnyEntry()); visits root,A,B,C,D,E,F in any order. 

Back