dune-typetree-2.8.0.tar.gz: .../typetree/visitor.hh

"Fossies" - the Fresh Open Source Software Archive

Member "dune-typetree-2.8.0/dune/typetree/visitor.hh" (31 Aug 2021, 22121 Bytes) of package /linux/misc/dune/dune-typetree-2.8.0.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "visitor.hh" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report:

2.8.0_vs_2.9.0.

1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- 2 // vi: set et ts=4 sw=2 sts=2: 3 4 #ifndef DUNE_TYPETREE_VISITOR_HH 5 #define DUNE_TYPETREE_VISITOR_HH 6 7 #include <dune/typetree/treepath.hh> 8 #include <dune/typetree/utility.hh> 9 10 namespace Dune { 11 namespace TypeTree { 12 13 /** \addtogroup Tree Traversal 14 * \ingroup TypeTree 15 * \{ 16 */ 17 18 //! Visitor interface and base class for TypeTree visitors. 19 /** 20 * DefaultVisitor defines the interface for visitors that can be applied to a TypeTree 21 * using applyToTree(). Each method of the visitor is passed a node of the tree (either as 22 * a mutable or a const reference, depending on the constness of the tree applyToTree() was 23 * called with). The second argument is of type TreePath and denotes the exact position of the 24 * node within the TypeTree, encoded as child indices starting at the root node. 25 * 26 * In order to create a functioning visitor, an implementation will - in addition to providing the methods 27 * of this class - also have to contain the following template struct, which is used to determine 28 * whether to visit a given node: 29 * 30 * \code 31 * template<typename Node, typename Child, typename TreePath> 32 * struct VisitChild 33 * { 34 * static const bool value = ...; // decide whether to visit Child 35 * }; 36 * \endcode 37 * 38 * For the two most common scenarios - visiting only direct children and visiting the whole tree - there 39 * are mixin classes VisitDirectChildren and VisitTree and combined base classes TreeVisitor and 40 * DirectChildrenVisitor. The latter two inherit from both DefaultVisitor and one of the two mixin classes 41 * and can thus be used as convenient base classes. 42 * 43 * \note This class can also be used as a convenient base class if the implemented visitor 44 * only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code. 45 */ 46 struct DefaultVisitor 47 { 48 49 //! Method for prefix tree traversal. 50 /** 51 * This method gets called when first encountering a non-leaf node and 52 * before visiting any of its children. 53 * 54 * \param t The node to visit. 55 * \param treePath The position of the node within the TypeTree. 56 */ 57 template<typename T, typename TreePath> 58 void pre(T&& t, TreePath treePath) const {} 59 60 //! Method for infix tree traversal. 61 /** 62 * This method gets called BETWEEN visits of children of a non-leaf node. 63 * That definition implies that this method will only be called for nodes 64 * with at least two children. 65 * 66 * \param t The node to visit. 67 * \param treePath The position of the node within the TypeTree. 68 */ 69 template<typename T, typename TreePath> 70 void in(T&& t, TreePath treePath) const {} 71 72 //! Method for postfix tree traversal. 73 /** 74 * This method gets called after all children of a non-leaf node have 75 * been visited. 76 * 77 * \param t The node to visit. 78 * \param treePath The position of the node within the TypeTree. 79 */ 80 template<typename T, typename TreePath> 81 void post(T&& t, TreePath treePath) const {} 82 83 //! Method for leaf traversal. 84 /** 85 * This method gets called when encountering a leaf node within the TypeTree. 86 * 87 * \param t The node to visit. 88 * \param treePath The position of the node within the TypeTree. 89 */ 90 template<typename T, typename TreePath> 91 void leaf(T&& t, TreePath treePath) const {} 92 93 //! Method for parent-child traversal. 94 /** 95 * This method gets called before visiting a child node. 96 * 97 * \note This method gets called even if the visitor decides not to visit the child in question. 98 * 99 * \param t The parent node. 100 * \param child The child node that will (potentially) be visited next. 101 * \param treePath The position of the parent node within the TypeTree. 102 * \param childIndex The index of the child node in relation to the parent node. 103 */ 104 template<typename T, typename Child, typename TreePath, typename ChildIndex> 105 void beforeChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex) const {} 106 107 //! Method for child-parent traversal. 108 /** 109 * This method gets called after visiting a child node. 110 * 111 * \note This method gets called even if the child node was not visited because the visitor 112 * chose not to do so. 113 * 114 * \param t The parent node. 115 * \param child The child node that was visited last (if the visitor did not reject it). 116 * \param treePath The position of the parent node within the TypeTree. 117 * \param childIndex The index of the child node in relation to the parent node. 118 */ 119 template<typename T, typename Child, typename TreePath, typename ChildIndex> 120 void afterChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex) const {} 121 122 }; 123 124 125 //! Visitor interface and base class for visitors of pairs of TypeTrees. 126 /** 127 * DefaultPairVisitor defines the interface for visitors that can be applied to a pair of TypeTrees 128 * using applyToTreePair(). Each method of the visitor is passed a node of both trees (either as 129 * a mutable or a const reference, depending on the constness of the tree applyToTreePair() was 130 * called with). The last argument is of type TreePath and denotes the exact position of the 131 * nodes within the TypeTrees, encoded as child indices starting at the root node. 132 * 133 * In order to create a functioning visitor, an implementation will - in addition to providing the methods 134 * of this class - also have to contain the following template struct, which is used to determine 135 * whether to visit a given node: 136 * 137 * \code 138 * template<typename Node1, 139 * typename Child1, 140 * typename Node2, 141 * typename Child2, 142 * typename TreePath> 143 * struct VisitChild 144 * { 145 * static const bool value = ...; // decide whether to visit Child 146 * }; 147 * \endcode 148 * 149 * For the two most common scenarios - visiting only direct children and visiting the whole tree - there 150 * are mixin classes VisitDirectChildren and VisitTree and combined base classes TreePairVisitor and 151 * DirectChildrenPairVisitor. The latter two inherit from both DefaultVisitor and one of the two mixin classes 152 * and can thus be used as convenient base classes. 153 * 154 * \note If your compiler does not support rvalue references, both trees must be either const or 155 * non-const. If you call applyToTreePair() with two trees of different constness, they will 156 * both be made const. 157 * 158 * \note This class can also be used as a convenient base class if the implemented visitor 159 * only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code. 160 */ 161 struct DefaultPairVisitor 162 { 163 164 //! Method for prefix tree traversal. 165 /** 166 * This method gets called when first encountering a non-leaf node and 167 * before visiting any of its children. 168 * 169 * \param t1 The node of the first tree to visit. 170 * \param t2 The node of the second tree to visit. 171 * \param treePath The position of the node within the TypeTree. 172 */ 173 template<typename T1, typename T2, typename TreePath> 174 void pre(T1&& t1, T2&& t2, TreePath treePath) const {} 175 176 //! Method for infix tree traversal. 177 /** 178 * This method gets called BETWEEN visits of children of a non-leaf node. 179 * That definition implies that this method will only be called for nodes 180 * with at least two children. 181 * 182 * \param t1 The node of the first tree to visit. 183 * \param t2 The node of the second tree to visit. 184 * \param treePath The position of the node within the TypeTree. 185 */ 186 template<typename T1, typename T2, typename TreePath> 187 void in(T1&& t1, T2&& t2, TreePath treePath) const {} 188 189 //! Method for postfix traversal. 190 /** 191 * This method gets called after all children of a non-leaf node have 192 * been visited. 193 * 194 * \param t1 The node of the first tree to visit. 195 * \param t2 The node of the second tree to visit. 196 * \param treePath The position of the node within the TypeTree. 197 */ 198 template<typename T1, typename T2, typename TreePath> 199 void post(T1&& t1, T2&& t2, TreePath treePath) const {} 200 201 //! Method for leaf traversal. 202 /** 203 * This method gets called when encountering a leaf node within the pair of TypeTrees. 204 * 205 * \attention Since the two TypeTrees are not required to be exactly identical, 206 * it is only guaranteed that at least one of the nodes is a leaf node, 207 * not both. 208 * 209 * \param t1 The node of the first tree to visit. 210 * \param t2 The node of the second tree to visit. 211 * \param treePath The position of the node within the TypeTree. 212 */ 213 template<typename T1, typename T2, typename TreePath> 214 void leaf(T1&& t1, T2&& t2, TreePath treePath) const {} 215 216 //! Method for parent-child traversal. 217 /** 218 * This method gets called before visiting a child node. 219 * 220 * \note This method gets called even if the visitor decides not to visit the child in question. 221 * 222 * \param t1 The node of the first tree to visit. 223 * \param child1 The child of t1 to visit. 224 * \param t2 The node of the second tree to visit. 225 * \param child2 The child of t2 to visit. 226 * \param treePath The position of the parent nodes within the TypeTree. 227 * \param childIndex The index of the child nodes in relation to the parent nodes. 228 */ 229 template<typename T1, typename Child1, typename T2, typename Child2, typename TreePath, typename ChildIndex> 230 void beforeChild(T1&& t1, Child1&& child1, T2&& t2, Child2&& child2, TreePath treePath, ChildIndex childIndex) const {} 231 232 //! Method for child-parent traversal. 233 /** 234 * This method gets called after visiting a child node. 235 * 236 * \note This method gets called even if the visitor decides not to visit the child in question. 237 * 238 * \param t1 The node of the first tree to visit. 239 * \param child1 The child of t1 to visit. 240 * \param t2 The node of the second tree to visit. 241 * \param child2 The child of t2 to visit. 242 * \param treePath The position of the parent nodes within the TypeTree. 243 * \param childIndex The index of the child nodes in relation to the parent nodes. 244 */ 245 template<typename T1, typename Child1, typename T2, typename Child2, typename TreePath, typename ChildIndex> 246 void afterChild(T1&& t1, Child1&& child1, T2&& t2, Child2&& child2, TreePath treePath, ChildIndex childIndex) const {} 247 248 }; 249 250 251 namespace Experimental { 252 253 /** 254 * @brief Hybrid visitor interface and base class for TypeTree hybrid visitors. 255 * 256 * DefaultHybridVisitor defines the interface for visitors that can be applied to a TypeTree 257 * using hybridApplyToTree(). Each method of the visitor is passed a node of the tree (either as 258 * a mutable or a const reference, depending on the constness of the tree hybridApplyToTree() was 259 * called with). The second argument is of type TreePath and denotes the exact position of the 260 * node within the TypeTree, encoded as child indices starting at the root node. 261 * 262 * An hybrid visitor is different from a plain visitor because each method receives a carried value 263 * (last argument) on the node visit and is required to return a transformed value from it. 264 * Transformations of the carried value type are allowed as long as they are expected on the 265 * next visited node. 266 * 267 * In order to create a functioning visitor, an implementation will - in addition to providing the methods 268 * of this class - also have to contain the following template struct, which is used to determine 269 * whether to visit a given node: 270 * 271 * \code 272 * template<typename Node, typename Child, typename TreePath> 273 * struct VisitChild 274 * { 275 * static const bool value = ...; // decide whether to visit Child 276 * }; 277 * \endcode 278 * 279 * 280 * \note This class can also be used as a convenient base class if the implemented visitor 281 * only needs to act on some of the possible callback sites, avoiding a lot of boilerplate code. 282 */ 283 struct DefaultHybridVisitor 284 { 285 286 /** 287 * \copybrief DefaultVisitor::pre 288 * \copydetails DefaultVisitor::pre 289 * 290 * \param u The carry value from previous visit. 291 * \return The result of applying this visitor to u. 292 */ 293 template<typename T, typename TreePath, typename U> 294 auto pre(T&& t, TreePath treePath, const U& u) const { return u;} 295 296 /** 297 * \copybrief DefaultVisitor::in 298 * \copydetails DefaultVisitor::in 299 * 300 * \param u The carry value from previous visit. 301 * \return The result of applying this visitor to u. 302 */ 303 template<typename T, typename TreePath, typename U> 304 auto in(T&& t, TreePath treePath, const U& u) const {return u;} 305 306 /** 307 * \copybrief DefaultVisitor::post 308 * \copydetails DefaultVisitor::post 309 * 310 * \param u The carry value from previous visit. 311 * \return The result of applying this visitor to u. 312 */ 313 template<typename T, typename TreePath, typename U> 314 auto post(T&& t, TreePath treePath, const U& u) const {return u;} 315 316 /** 317 * \copybrief DefaultVisitor::leaf 318 * \copydetails DefaultVisitor::leaf 319 * 320 * \param u The carry value from previous visit. 321 * \return The result of applying this visitor to u. 322 */ 323 template<typename T, typename TreePath, typename U> 324 auto leaf(T&& t, TreePath treePath, const U& u) const { return u;} 325 326 /** 327 * \copybrief DefaultVisitor::beforeChild 328 * \copydetails DefaultVisitor::beforeChild 329 * 330 * \param u The carry value from previous visit. 331 * \return The result of applying this visitor to u. 332 */ 333 template<typename T, typename Child, typename TreePath, typename ChildIndex, typename U> 334 auto beforeChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex, const U& u) const {return u;} 335 336 /** 337 * \copybrief DefaultVisitor::afterChild 338 * \copydetails DefaultVisitor::afterChild 339 * 340 * \param u The carry value from previous visit. 341 * \return The result of applying this visitor to u. 342 */ 343 template<typename T, typename Child, typename TreePath, typename ChildIndex, typename U> 344 auto afterChild(T&& t, Child&& child, TreePath treePath, ChildIndex childIndex, const U& u) const {return u;} 345 346 }; 347 } // namespace Experimental 348 349 //! Mixin base class for visitors that only want to visit the direct children of a node. 350 /** 351 * This mixin class will reject all children presented to it, causing the algorithm to 352 * only visit the root node and call DefaultVisitor::beforeChild() and DefaultVisitor::afterChild() 353 * for its direct children. 354 */ 355 struct VisitDirectChildren 356 { 357 358 // the little trick with the default template arguments 359 // makes the class usable for both single-tree visitors 360 // and visitors for pairs of trees 361 //! Template struct for determining whether or not to visit a given child. 362 template<typename Node1, 363 typename Child1, 364 typename Node2, 365 typename Child2 = void, 366 typename TreePath = void> 367 struct VisitChild 368 { 369 //! Do not visit any child. 370 static const bool value = false; 371 }; 372 373 }; 374 375 376 //! Mixin base class for visitors that want to visit the complete tree. 377 /** 378 * This mixin class will accept all children presented to it and thus make the iterator 379 * traverse the entire tree. 380 */ 381 struct VisitTree 382 { 383 384 // the little trick with the default template arguments 385 // makes the class usable for both single-tree visitors 386 // and visitors for pairs of trees 387 //! Template struct for determining whether or not to visit a given child. 388 template<typename Node1, 389 typename Child1, 390 typename Node2, 391 typename Child2 = void, 392 typename TreePath = void> 393 struct VisitChild 394 { 395 //! Visit any child. 396 static const bool value = true; 397 }; 398 399 }; 400 401 //! Mixin base class for visitors that require a static TreePath during traversal. 402 /** 403 * \warning Static traversal should only be used if absolutely necessary, as it tends 404 * to increase compilation times and object sizes (especially if compiling 405 * with debug information)! 406 * 407 * \sa DynamicTraversal 408 */ 409 struct StaticTraversal 410 { 411 //! Use the static tree traversal algorithm. 412 static const TreePathType::Type treePathType = TreePathType::fullyStatic; 413 }; 414 415 //! Mixin base class for visitors that only need a dynamic TreePath during traversal. 416 /** 417 * \note Dynamic traversal is preferable to static traversal, as it causes fewer 418 * template instantiations, which improves compile time and reduces object 419 * size (especially if compiling with debug information). 420 * 421 * \sa StaticTraversal 422 */ 423 struct DynamicTraversal 424 { 425 //! Use the dynamic tree traversal algorithm. 426 static const TreePathType::Type treePathType = TreePathType::dynamic; 427 }; 428 429 //! Convenience base class for visiting the entire tree. 430 struct TreeVisitor 431 : public DefaultVisitor 432 , public VisitTree 433 {}; 434 435 //! Convenience base class for visiting the direct children of a node. 436 struct DirectChildrenVisitor 437 : public DefaultVisitor 438 , public VisitDirectChildren 439 {}; 440 441 //! Convenience base class for visiting an entire tree pair. 442 struct TreePairVisitor 443 : public DefaultPairVisitor 444 , public VisitTree 445 {}; 446 447 //! Convenience base class for visiting the direct children of a node pair. 448 struct DirectChildrenPairVisitor 449 : public DefaultPairVisitor 450 , public VisitDirectChildren 451 {}; 452 453 namespace Experimental::Info { 454 455 struct LeafCounterVisitor 456 : public DefaultHybridVisitor 457 , public StaticTraversal 458 , public VisitTree 459 { 460 template<class Tree, class Child, class TreePath, class ChildIndex, class U> 461 auto beforeChild(Tree&&, Child&&, TreePath, ChildIndex, U u) const { 462 // in this case child index is an integral constant: forward u 463 return u; 464 } 465 466 template<class Tree, class Child, class TreePath, class U> 467 std::size_t beforeChild(Tree&&, Child&&, TreePath, std::size_t childIndex, U u) const { 468 // in this case child index is a run-time index: cast accumulated u to std::size_t 469 return std::size_t{u}; 470 } 471 472 template<class Tree, class TreePath, class U> 473 auto leaf(Tree&&, TreePath, U u) const 474 { 475 return Hybrid::plus(u,Dune::Indices::_1); 476 } 477 478 }; 479 480 struct NodeCounterVisitor 481 : public LeafCounterVisitor 482 { 483 template<typename Tree, typename TreePath, typename U> 484 auto pre(Tree&& tree, TreePath treePath, U u) const { 485 return Hybrid::plus(u,Indices::_1); 486 } 487 }; 488 489 struct DepthVisitor 490 : public DefaultHybridVisitor 491 , public StaticTraversal 492 , public VisitTree 493 { 494 template<class Tree, class TreePath, class U> 495 auto leaf(Tree&&, TreePath, U u) const 496 { 497 auto path_size = index_constant<treePathSize(TreePath{})>{}; 498 auto depth = Hybrid::plus(path_size,Indices::_1); 499 return Hybrid::max(depth,u); 500 } 501 }; 502 503 //! The depth of the TypeTree. 504 // result is alwayas an integral constant 505 template<typename Tree> 506 auto depth(const Tree& tree) 507 { 508 return hybridApplyToTree(tree,DepthVisitor{},Indices::_0); 509 } 510 511 //! The depth of the Tree. 512 // return types is std::integral_constant. 513 template<typename Tree> 514 constexpr auto depth() 515 { 516 return decltype(hybridApplyToTree(std::declval<Tree>(),DepthVisitor{},Indices::_0)){}; 517 } 518 519 //! The total number of nodes in the Tree. 520 // if Tree is dynamic, return type is std::size_t, otherwise std::integral_constant. 521 template<typename Tree> 522 auto nodeCount(const Tree& tree) 523 { 524 return hybridApplyToTree(tree,NodeCounterVisitor{},Indices::_0); 525 } 526 527 //! The number of leaf nodes in the Tree. 528 // if Tree is dynamic, return type is std::size_t, otherwise std::integral_constant. 529 template<typename Tree> 530 auto leafCount(const Tree& tree) 531 { 532 return hybridApplyToTree(tree,LeafCounterVisitor{},Dune::Indices::_0); 533 } 534 535 //! true if any of the nodes in the tree only has dynamic degree. 536 template<typename Tree> 537 constexpr bool isDynamic = std::is_same<std::size_t, decltype(leafCount(std::declval<Tree>()))>{}; 538 539 } // namespace Experimental::Info 540 541 //! \} group Tree Traversal 542 543 } // namespace TypeTree 544 } //namespace Dune 545 546 #endif // DUNE_TYPETREE_VISITOR_HH