HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NodeManager.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /// @file tree/NodeManager.h
5 ///
6 /// @authors Ken Museth, Dan Bailey
7 ///
8 /// @brief NodeManager produces linear arrays of all tree nodes
9 /// allowing for efficient threading and bottom-up processing.
10 ///
11 /// @note A NodeManager can be constructed from a Tree or LeafManager.
12 
13 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
14 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
15 
16 #include <openvdb/Types.h>
17 #include <tbb/parallel_for.h>
18 #include <tbb/parallel_reduce.h>
19 #include <deque>
20 
21 
22 namespace openvdb {
24 namespace OPENVDB_VERSION_NAME {
25 namespace tree {
26 
27 // Produce linear arrays of all tree nodes, to facilitate efficient threading
28 // and bottom-up processing.
29 template<typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
31 
32 
33 // Produce linear arrays of all tree nodes lazily, to facilitate efficient threading
34 // of topology-changing top-down workflows.
35 template<typename TreeOrLeafManagerT, Index _LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
37 
38 
39 ////////////////////////////////////////
40 
41 
42 // This is a dummy node filtering class used by the NodeManager class to match
43 // the internal filtering interface used by the DynamicNodeManager.
44 struct NodeFilter
45 {
46  static bool valid(size_t) { return true; }
47 }; // struct NodeFilter
48 
49 
50 /// @brief This class caches tree nodes of a specific type in a linear array.
51 ///
52 /// @note It is for internal use and should rarely be used directly.
53 template<typename NodeT>
54 class NodeList
55 {
56 public:
57  NodeList() = default;
58 
59  NodeT& operator()(size_t n) const { assert(n<mNodeCount); return *(mNodes[n]); }
60 
61  NodeT*& operator[](size_t n) { assert(n<mNodeCount); return mNodes[n]; }
62 
63  Index64 nodeCount() const { return mNodeCount; }
64 
65  void clear()
66  {
67  mNodePtrs.reset();
68  mNodes = nullptr;
69  mNodeCount = 0;
70  }
71 
72  // initialize this node list from the provided root node
73  template <typename RootT>
74  bool initRootChildren(RootT& root)
75  {
76  // Allocate (or deallocate) the node pointer array
77 
78  size_t nodeCount = root.childCount();
79 
80  if (nodeCount != mNodeCount) {
81  if (nodeCount > 0) {
82  mNodePtrs.reset(new NodeT*[nodeCount]);
83  mNodes = mNodePtrs.get();
84  } else {
85  mNodePtrs.reset();
86  mNodes = nullptr;
87  }
89  }
90 
91  if (mNodeCount == 0) return false;
92 
93  // Populate the node pointers
94 
95  NodeT** nodePtr = mNodes;
96  for (auto iter = root.beginChildOn(); iter; ++iter) {
97  *nodePtr++ = &iter.getValue();
98  }
99 
100  return true;
101  }
102 
103  // initialize this node list from another node list containing the parent nodes
104  template <typename ParentsT, typename NodeFilterT>
105  bool initNodeChildren(ParentsT& parents, const NodeFilterT& nodeFilter = NodeFilterT(), bool serial = false)
106  {
107  // Compute the node counts for each node
108 
109  std::vector<Index32> nodeCounts;
110  if (serial) {
111  nodeCounts.reserve(parents.nodeCount());
112  for (size_t i = 0; i < parents.nodeCount(); i++) {
113  if (!nodeFilter.valid(i)) nodeCounts.push_back(0);
114  else nodeCounts.push_back(parents(i).childCount());
115  }
116  } else {
117  nodeCounts.resize(parents.nodeCount());
119  // with typical node sizes and SSE enabled, there are only a handful
120  // of instructions executed per-operation with a default grainsize
121  // of 1, so increase to 64 to reduce parallel scheduling overhead
122  tbb::blocked_range<Index64>(0, parents.nodeCount(), /*grainsize=*/64),
123  [&](tbb::blocked_range<Index64>& range)
124  {
125  for (Index64 i = range.begin(); i < range.end(); i++) {
126  if (!nodeFilter.valid(i)) nodeCounts[i] = 0;
127  else nodeCounts[i] = parents(i).childCount();
128  }
129  }
130  );
131  }
132 
133  // Turn node counts into a cumulative histogram and obtain total node count
134 
135  for (size_t i = 1; i < nodeCounts.size(); i++) {
136  nodeCounts[i] += nodeCounts[i-1];
137  }
138 
139  const size_t nodeCount = nodeCounts.empty() ? 0 : nodeCounts.back();
140 
141  // Allocate (or deallocate) the node pointer array
142 
143  if (nodeCount != mNodeCount) {
144  if (nodeCount > 0) {
145  mNodePtrs.reset(new NodeT*[nodeCount]);
146  mNodes = mNodePtrs.get();
147  } else {
148  mNodePtrs.reset();
149  mNodes = nullptr;
150  }
152  }
153 
154  if (mNodeCount == 0) return false;
155 
156  // Populate the node pointers
157 
158  if (serial) {
159  NodeT** nodePtr = mNodes;
160  for (size_t i = 0; i < parents.nodeCount(); i++) {
161  if (!nodeFilter.valid(i)) continue;
162  for (auto iter = parents(i).beginChildOn(); iter; ++iter) {
163  *nodePtr++ = &iter.getValue();
164  }
165  }
166  } else {
168  tbb::blocked_range<Index64>(0, parents.nodeCount()),
169  [&](tbb::blocked_range<Index64>& range)
170  {
171  Index64 i = range.begin();
172  NodeT** nodePtr = mNodes;
173  if (i > 0) nodePtr += nodeCounts[i-1];
174  for ( ; i < range.end(); i++) {
175  if (!nodeFilter.valid(i)) continue;
176  for (auto iter = parents(i).beginChildOn(); iter; ++iter) {
177  *nodePtr++ = &iter.getValue();
178  }
179  }
180  }
181  );
182  }
183 
184  return true;
185  }
186 
187  class NodeRange
188  {
189  public:
190 
191  NodeRange(size_t begin, size_t end, const NodeList& nodeList, size_t grainSize=1):
192  mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
193 
195  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
196  mNodeList(r.mNodeList) {}
197 
198  size_t size() const { return mEnd - mBegin; }
199 
200  size_t grainsize() const { return mGrainSize; }
201 
202  const NodeList& nodeList() const { return mNodeList; }
203 
204  bool empty() const {return !(mBegin < mEnd);}
205 
206  bool is_divisible() const {return mGrainSize < this->size();}
207 
208  class Iterator
209  {
210  public:
211  Iterator(const NodeRange& range, size_t pos): mRange(range), mPos(pos)
212  {
213  assert(this->isValid());
214  }
215  Iterator(const Iterator&) = default;
216  Iterator& operator=(const Iterator&) = default;
217  /// Advance to the next node.
218  Iterator& operator++() { ++mPos; return *this; }
219  /// Return a reference to the node to which this iterator is pointing.
220  NodeT& operator*() const { return mRange.mNodeList(mPos); }
221  /// Return a pointer to the node to which this iterator is pointing.
222  NodeT* operator->() const { return &(this->operator*()); }
223  /// Return the index into the list of the current node.
224  size_t pos() const { return mPos; }
225  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
226  /// Return @c true if this iterator is not yet exhausted.
227  bool test() const { return mPos < mRange.mEnd; }
228  /// Return @c true if this iterator is not yet exhausted.
229  operator bool() const { return this->test(); }
230  /// Return @c true if this iterator is exhausted.
231  bool empty() const { return !this->test(); }
232  bool operator!=(const Iterator& other) const
233  {
234  return (mPos != other.mPos) || (&mRange != &other.mRange);
235  }
236  bool operator==(const Iterator& other) const { return !(*this != other); }
237  const NodeRange& nodeRange() const { return mRange; }
238 
239  private:
240  const NodeRange& mRange;
241  size_t mPos;
242  };// NodeList::NodeRange::Iterator
243 
244  Iterator begin() const {return Iterator(*this, mBegin);}
245 
246  Iterator end() const {return Iterator(*this, mEnd);}
247 
248  private:
249  size_t mEnd, mBegin, mGrainSize;
250  const NodeList& mNodeList;
251 
252  static size_t doSplit(NodeRange& r)
253  {
254  assert(r.is_divisible());
255  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
256  r.mEnd = middle;
257  return middle;
258  }
259  };// NodeList::NodeRange
260 
261  /// Return a TBB-compatible NodeRange.
262  NodeRange nodeRange(size_t grainsize = 1) const
263  {
264  return NodeRange(0, this->nodeCount(), *this, grainsize);
265  }
266 
267  template<typename NodeOp>
268  void foreach(const NodeOp& op, bool threaded = true, size_t grainSize=1)
269  {
270  NodeTransformerCopy<NodeOp> transform(op); // always deep-copies the op
271  transform.run(this->nodeRange(grainSize), threaded);
272  }
273 
274  template<typename NodeOp>
275  void reduce(NodeOp& op, bool threaded = true, size_t grainSize=1)
276  {
277  NodeReducer<NodeOp> transform(op);
278  transform.run(this->nodeRange(grainSize), threaded);
279  }
280 
281  // identical to foreach except the operator() method has a node index and
282  // the operator is referenced instead of copied in NodeTransformer
283  template<typename NodeOp>
284  void foreachWithIndex(const NodeOp& op, bool threaded = true, size_t grainSize=1)
285  {
286  NodeTransformer<NodeOp, OpWithIndex> transform(op);
287  transform.run(this->nodeRange(grainSize), threaded);
288  }
289 
290  // identical to reduce except the operator() method has a node index
291  template<typename NodeOp>
292  void reduceWithIndex(NodeOp& op, bool threaded = true, size_t grainSize=1)
293  {
294  NodeReducer<NodeOp, OpWithIndex> transform(op);
295  transform.run(this->nodeRange(grainSize), threaded);
296  }
297 
298 private:
299 
300  // default execution in the NodeManager ignores the node index
301  // given by the iterator position
302  struct OpWithoutIndex
303  {
304  template <typename T>
305  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter); }
306  };
307 
308  // execution in the DynamicNodeManager matches that of the LeafManager in
309  // passing through the node index given by the iterator position
310  struct OpWithIndex
311  {
312  template <typename T>
313  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter, iter.pos()); }
314  };
315 
316  // Private struct of NodeList that performs parallel_for
317  template<typename NodeOp, typename OpT = OpWithoutIndex>
318  struct NodeTransformerCopy
319  {
320  NodeTransformerCopy(const NodeOp& nodeOp) : mNodeOp(nodeOp)
321  {
322  }
323  void run(const NodeRange& range, bool threaded = true)
324  {
325  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
326  }
327  void operator()(const NodeRange& range) const
328  {
329  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
330  OpT::template eval(mNodeOp, it);
331  }
332  }
333  const NodeOp mNodeOp;
334  };// NodeList::NodeTransformerCopy
335 
336  // Private struct of NodeList that performs parallel_for
337  template<typename NodeOp, typename OpT = OpWithoutIndex>
338  struct NodeTransformer
339  {
340  NodeTransformer(const NodeOp& nodeOp) : mNodeOp(nodeOp)
341  {
342  }
343  void run(const NodeRange& range, bool threaded = true)
344  {
345  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
346  }
347  void operator()(const NodeRange& range) const
348  {
349  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
350  OpT::template eval(mNodeOp, it);
351  }
352  }
353  const NodeOp& mNodeOp;
354  };// NodeList::NodeTransformer
355 
356  // Private struct of NodeList that performs parallel_reduce
357  template<typename NodeOp, typename OpT = OpWithoutIndex>
358  struct NodeReducer
359  {
360  NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp)
361  {
362  }
363  NodeReducer(const NodeReducer& other, tbb::split)
364  : mNodeOpPtr(std::make_unique<NodeOp>(*(other.mNodeOp), tbb::split()))
365  , mNodeOp(mNodeOpPtr.get())
366  {
367  }
368  void run(const NodeRange& range, bool threaded = true)
369  {
370  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
371  }
372  void operator()(const NodeRange& range)
373  {
374  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
375  OpT::template eval(*mNodeOp, it);
376  }
377  }
378  void join(const NodeReducer& other)
379  {
380  mNodeOp->join(*(other.mNodeOp));
381  }
382  std::unique_ptr<NodeOp> mNodeOpPtr;
383  NodeOp *mNodeOp = nullptr;
384  };// NodeList::NodeReducer
385 
386 
387 protected:
388  size_t mNodeCount = 0;
389  std::unique_ptr<NodeT*[]> mNodePtrs;
390  NodeT** mNodes = nullptr;
391 };// NodeList
392 
393 
394 /////////////////////////////////////////////
395 
396 
397 /// @brief This class is a link in a chain that each caches tree nodes
398 /// of a specific type in a linear array.
399 ///
400 /// @note It is for internal use and should rarely be used directly.
401 template<typename NodeT, Index LEVEL>
403 {
404 public:
405  using NonConstChildNodeType = typename NodeT::ChildNodeType;
407 
408  NodeManagerLink() = default;
409 
410  void clear() { mList.clear(); mNext.clear(); }
411 
412  template <typename RootT>
413  void initRootChildren(RootT& root, bool serial = false)
414  {
415  mList.initRootChildren(root);
416  mNext.initNodeChildren(mList, serial);
417  }
418 
419  template<typename ParentsT>
420  void initNodeChildren(ParentsT& parents, bool serial = false)
421  {
422  mList.initNodeChildren(parents, NodeFilter(), serial);
423  mNext.initNodeChildren(mList, serial);
424  }
425 
426  Index64 nodeCount() const { return mList.nodeCount() + mNext.nodeCount(); }
427 
429  {
430  return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
431  }
432 
433  template<typename NodeOp>
434  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
435  {
436  mNext.foreachBottomUp(op, threaded, grainSize);
437  mList.foreach(op, threaded, grainSize);
438  }
439 
440  template<typename NodeOp>
441  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
442  {
443  mList.foreach(op, threaded, grainSize);
444  mNext.foreachTopDown(op, threaded, grainSize);
445  }
446 
447  template<typename NodeOp>
448  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
449  {
450  mNext.reduceBottomUp(op, threaded, grainSize);
451  mList.reduce(op, threaded, grainSize);
452  }
453 
454  template<typename NodeOp>
455  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
456  {
457  mList.reduce(op, threaded, grainSize);
458  mNext.reduceTopDown(op, threaded, grainSize);
459  }
460 
461 protected:
464 };// NodeManagerLink class
465 
466 
467 ////////////////////////////////////////
468 
469 
470 /// @private
471 /// @brief Specialization that terminates the chain of cached tree nodes
472 /// @note It is for internal use and should rarely be used directly.
473 template<typename NodeT>
474 class NodeManagerLink<NodeT, 0>
475 {
476 public:
477  NodeManagerLink() = default;
478 
479  /// @brief Clear all the cached tree nodes
480  void clear() { mList.clear(); }
481 
482  template <typename RootT>
483  void initRootChildren(RootT& root, bool /*serial*/ = false) { mList.initRootChildren(root); }
484 
485  template<typename ParentsT>
486  void initNodeChildren(ParentsT& parents, bool serial = false) { mList.initNodeChildren(parents, NodeFilter(), serial); }
487 
488  Index64 nodeCount() const { return mList.nodeCount(); }
489 
490  Index64 nodeCount(Index) const { return mList.nodeCount(); }
491 
492  template<typename NodeOp>
493  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
494  {
495  mList.foreach(op, threaded, grainSize);
496  }
497 
498  template<typename NodeOp>
499  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
500  {
501  mList.foreach(op, threaded, grainSize);
502  }
503 
504  template<typename NodeOp>
505  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
506  {
507  mList.reduce(op, threaded, grainSize);
508  }
509 
510  template<typename NodeOp>
511  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
512  {
513  mList.reduce(op, threaded, grainSize);
514  }
515 
516 protected:
517  NodeList<NodeT> mList;
518 };// NodeManagerLink class
519 
520 
521 ////////////////////////////////////////
522 
523 
524 /// @brief To facilitate threading over the nodes of a tree, cache
525 /// node pointers in linear arrays, one for each level of the tree.
526 ///
527 /// @details This implementation works with trees of any depth, but
528 /// optimized specializations are provided for the most typical tree depths.
529 template<typename TreeOrLeafManagerT, Index _LEVELS>
530 class NodeManager
531 {
532 public:
533  static const Index LEVELS = _LEVELS;
534  static_assert(LEVELS > 0,
535  "expected instantiation of template specialization"); // see specialization below
536  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
538  using NonConstChildNodeType = typename RootNodeType::ChildNodeType;
540  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
541 
542  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
543  : mRoot(tree.root())
544  {
545  this->rebuild(serial);
546  }
547 
548  NodeManager(const NodeManager&) = delete;
549 
550  /// @brief Clear all the cached tree nodes
551  void clear() { mChain.clear(); }
552 
553  /// @brief Clear and recache all the tree nodes from the
554  /// tree. This is required if tree nodes have been added or removed.
555  void rebuild(bool serial = false) { mChain.initRootChildren(mRoot, serial); }
556 
557  /// @brief Return a reference to the root node.
558  const RootNodeType& root() const { return mRoot; }
559 
560  /// @brief Return the total number of cached nodes (excluding the root node)
561  Index64 nodeCount() const { return mChain.nodeCount(); }
562 
563  /// @brief Return the number of cached nodes at level @a i, where
564  /// 0 corresponds to the lowest level.
565  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
566 
567  //@{
568  /// @brief Threaded method that applies a user-supplied functor
569  /// to all the nodes in the tree.
570  ///
571  /// @param op user-supplied functor, see examples for interface details.
572  /// @param threaded optional toggle to disable threading, on by default.
573  /// @param grainSize optional parameter to specify the grainsize
574  /// for threading, one by default.
575  ///
576  /// @warning The functor object is deep-copied to create TBB tasks.
577  ///
578  /// @par Example:
579  /// @code
580  /// // Functor to offset all the inactive values of a tree. Note
581  /// // this implementation also illustrates how different
582  /// // computation can be applied to the different node types.
583  /// template<typename TreeType>
584  /// struct OffsetOp
585  /// {
586  /// using ValueT = typename TreeT::ValueType;
587  /// using RootT = typename TreeT::RootNodeType;
588  /// using LeafT = typename TreeT::LeafNodeType;
589  /// OffsetOp(const ValueT& v) : mOffset(v) {}
590  ///
591  /// // Processes the root node. Required by the NodeManager
592  /// void operator()(RootT& root) const
593  /// {
594  /// for (typename RootT::ValueOffIter i = root.beginValueOff(); i; ++i) *i += mOffset;
595  /// }
596  /// // Processes the leaf nodes. Required by the NodeManager
597  /// void operator()(LeafT& leaf) const
598  /// {
599  /// for (typename LeafT::ValueOffIter i = leaf.beginValueOff(); i; ++i) *i += mOffset;
600  /// }
601  /// // Processes the internal nodes. Required by the NodeManager
602  /// template<typename NodeT>
603  /// void operator()(NodeT& node) const
604  /// {
605  /// for (typename NodeT::ValueOffIter i = node.beginValueOff(); i; ++i) *i += mOffset;
606  /// }
607  /// private:
608  /// const ValueT mOffset;
609  /// };
610  ///
611  /// // usage:
612  /// OffsetOp<FloatTree> op(3.0f);
613  /// tree::NodeManager<FloatTree> nodes(tree);
614  /// nodes.foreachBottomUp(op);
615  ///
616  /// // or if a LeafManager already exists
617  /// using T = tree::LeafManager<FloatTree>;
618  /// OffsetOp<T> op(3.0f);
619  /// tree::NodeManager<T> nodes(leafManager);
620  /// nodes.foreachBottomUp(op);
621  ///
622  /// @endcode
623  template<typename NodeOp>
624  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
625  {
626  mChain.foreachBottomUp(op, threaded, grainSize);
627  op(mRoot);
628  }
629 
630  template<typename NodeOp>
631  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
632  {
633  op(mRoot);
634  mChain.foreachTopDown(op, threaded, grainSize);
635  }
636 
637  //@}
638 
639  //@{
640  /// @brief Threaded method that processes nodes with a user supplied functor
641  ///
642  /// @param op user-supplied functor, see examples for interface details.
643  /// @param threaded optional toggle to disable threading, on by default.
644  /// @param grainSize optional parameter to specify the grainsize
645  /// for threading, one by default.
646  ///
647  /// @warning The functor object is deep-copied to create TBB tasks.
648  ///
649  /// @par Example:
650  /// @code
651  /// // Functor to count nodes in a tree
652  /// template<typename TreeType>
653  /// struct NodeCountOp
654  /// {
655  /// NodeCountOp() : nodeCount(TreeType::DEPTH, 0), totalCount(0)
656  /// {
657  /// }
658  /// NodeCountOp(const NodeCountOp& other, tbb::split) :
659  /// nodeCount(TreeType::DEPTH, 0), totalCount(0)
660  /// {
661  /// }
662  /// void join(const NodeCountOp& other)
663  /// {
664  /// for (size_t i = 0; i < nodeCount.size(); ++i) {
665  /// nodeCount[i] += other.nodeCount[i];
666  /// }
667  /// totalCount += other.totalCount;
668  /// }
669  /// // do nothing for the root node
670  /// void operator()(const typename TreeT::RootNodeType& node)
671  /// {
672  /// }
673  /// // count the internal and leaf nodes
674  /// template<typename NodeT>
675  /// void operator()(const NodeT& node)
676  /// {
677  /// ++(nodeCount[NodeT::LEVEL]);
678  /// ++totalCount;
679  /// }
680  /// std::vector<openvdb::Index64> nodeCount;
681  /// openvdb::Index64 totalCount;
682  /// };
683  ///
684  /// // usage:
685  /// NodeCountOp<FloatTree> op;
686  /// tree::NodeManager<FloatTree> nodes(tree);
687  /// nodes.reduceBottomUp(op);
688  ///
689  /// // or if a LeafManager already exists
690  /// NodeCountOp<FloatTree> op;
691  /// using T = tree::LeafManager<FloatTree>;
692  /// T leafManager(tree);
693  /// tree::NodeManager<T> nodes(leafManager);
694  /// nodes.reduceBottomUp(op);
695  ///
696  /// @endcode
697  template<typename NodeOp>
698  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
699  {
700  mChain.reduceBottomUp(op, threaded, grainSize);
701  op(mRoot);
702  }
703 
704  template<typename NodeOp>
705  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
706  {
707  op(mRoot);
708  mChain.reduceTopDown(op, threaded, grainSize);
709  }
710  //@}
711 
712 protected:
715 };// NodeManager class
716 
717 
718 ////////////////////////////////////////////
719 
720 
721 // Wraps a user-supplied DynamicNodeManager operator and stores the return
722 // value of the operator() method to the index of the node in a bool array
723 template <typename OpT>
725 {
726  explicit ForeachFilterOp(const OpT& op, openvdb::Index64 size)
727  : mOp(op)
728  , mValidPtr(std::make_unique<bool[]>(size))
729  , mValid(mValidPtr.get()) { }
730 
732  : mOp(other.mOp)
733  , mValid(other.mValid) { }
734 
735  template<typename NodeT>
736  void operator()(NodeT& node, size_t idx) const
737  {
738  mValid[idx] = mOp(node, idx);
739  }
740 
741  bool valid(size_t idx) const { return mValid[idx]; }
742 
743  const OpT& op() const { return mOp; }
744 
745 private:
746  const OpT& mOp;
747  std::unique_ptr<bool[]> mValidPtr;
748  bool* mValid = nullptr;
749 }; // struct ForeachFilterOp
750 
751 
752 // Wraps a user-supplied DynamicNodeManager operator and stores the return
753 // value of the operator() method to the index of the node in a bool array
754 template <typename OpT>
756 {
758  : mOp(&op)
759  , mValidPtr(std::make_unique<bool[]>(size))
760  , mValid(mValidPtr.get()) { }
761 
763  : mOp(other.mOp)
764  , mValid(other.mValid) { }
765 
767  : mOpPtr(std::make_unique<OpT>(*(other.mOp), tbb::split()))
768  , mOp(mOpPtr.get())
769  , mValid(other.mValid) { }
770 
771  template<typename NodeT>
772  void operator()(NodeT& node, size_t idx) const
773  {
774  mValid[idx] = (*mOp)(node, idx);
775  }
776 
777  void join(const ReduceFilterOp& other)
778  {
779  mOp->join(*(other.mOp));
780  }
781 
782  bool valid(size_t idx) const
783  {
784  return mValid[idx];
785  }
786 
787  OpT& op() { return *mOp; }
788 
789 private:
790  std::unique_ptr<OpT> mOpPtr;
791  OpT* mOp = nullptr;
792  std::unique_ptr<bool[]> mValidPtr;
793  bool* mValid = nullptr;
794 }; // struct ReduceFilterOp
795 
796 
797 /// @brief This class is a link in a chain that each caches tree nodes
798 /// of a specific type in a linear array.
799 ///
800 /// @note It is for internal use and should rarely be used directly.
801 template<typename NodeT, Index LEVEL>
803 {
804 public:
805  DynamicNodeManagerLink() = default;
806 
807  template<typename NodeOpT, typename RootT>
808  void foreachTopDown(const NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
809  {
810  if (!op(root, /*index=*/0)) return;
811  if (!mList.initRootChildren(root)) return;
812  ForeachFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
813  mList.foreachWithIndex(filterOp, threaded, grainSize);
814  mNext.foreachTopDownRecurse(filterOp, mList, threaded, grainSize);
815  }
816 
817  template<typename FilterOpT, typename ParentT>
818  void foreachTopDownRecurse(const FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
819  {
820  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
821  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
822  mList.foreachWithIndex(childFilterOp, threaded, grainSize);
823  }
824 
825  template<typename NodeOpT, typename RootT>
826  void reduceTopDown(NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
827  {
828  if (!op(root, /*index=*/0)) return;
829  if (!mList.initRootChildren(root)) return;
830  ReduceFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
831  mList.reduceWithIndex(filterOp, threaded, grainSize);
832  mNext.reduceTopDownRecurse(filterOp, mList, threaded, grainSize);
833  }
834 
835  template<typename FilterOpT, typename ParentT>
836  void reduceTopDownRecurse(FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
837  {
838  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
839  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
840  mList.reduceWithIndex(childFilterOp, threaded, grainSize);
841  }
842 
843 protected:
845  DynamicNodeManagerLink<typename NodeT::ChildNodeType, LEVEL-1> mNext;
846 };// DynamicNodeManagerLink class
847 
848 
849 /// @private
850 /// @brief Specialization that terminates the chain of cached tree nodes
851 /// @note It is for internal use and should rarely be used directly.
852 template<typename NodeT>
853 class DynamicNodeManagerLink<NodeT, 0>
854 {
855 public:
856  DynamicNodeManagerLink() = default;
857 
858  template<typename NodeFilterOp, typename ParentT>
859  void foreachTopDownRecurse(const NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
860  {
861  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
862  mList.foreachWithIndex(nodeFilterOp.op(), threaded, grainSize);
863  }
864 
865  template<typename NodeFilterOp, typename ParentT>
866  void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
867  {
868  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
869  mList.reduceWithIndex(nodeFilterOp.op(), threaded, grainSize);
870  }
871 
872 protected:
873  NodeList<NodeT> mList;
874 };// DynamicNodeManagerLink class
875 
876 
877 template<typename TreeOrLeafManagerT, Index _LEVELS>
878 class DynamicNodeManager
879 {
880 public:
881  static const Index LEVELS = _LEVELS;
882  static_assert(LEVELS > 0,
883  "expected instantiation of template specialization"); // see specialization below
884  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
885  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
886 
887  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
888 
889  DynamicNodeManager(const DynamicNodeManager&) = delete;
890 
891  /// @brief Return a reference to the root node.
892  const RootNodeType& root() const { return mRoot; }
893 
894  /// @brief Threaded method that applies a user-supplied functor
895  /// to all the nodes in the tree.
896  ///
897  /// @param op user-supplied functor, see examples for interface details.
898  /// @param threaded optional toggle to disable threading, on by default.
899  /// @param grainSize optional parameter to specify the grainsize
900  /// for threading, one by default.
901  ///
902  /// @note There are two key differences to the interface of the
903  /// user-supplied functor to the NodeManager class - (1) the operator()
904  /// method aligns with the LeafManager class in expecting the index of the
905  /// node in a linear array of identical node types, (2) the operator()
906  /// method returns a boolean termination value with true indicating that
907  /// children of this node should be processed, false indicating the
908  /// early-exit termination should occur.
909  ///
910  /// @note Unlike the NodeManager, the foreach() method of the
911  /// DynamicNodeManager uses copy-by-reference for the user-supplied functor.
912  /// This can be an issue when using a shared Accessor or shared Sampler in
913  /// the operator as they are not inherently thread-safe. For these use
914  /// cases, it is recommended to create the Accessor or Sampler in the
915  /// operator execution itself.
916  ///
917  /// @par Example:
918  /// @code
919  /// // Functor to densify the first child node in a linear array. Note
920  /// // this implementation also illustrates how different
921  /// // computation can be applied to the different node types.
922  ///
923  /// template<typename TreeT>
924  /// struct DensifyOp
925  /// {
926  /// using RootT = typename TreeT::RootNodeType;
927  /// using LeafT = typename TreeT::LeafNodeType;
928  ///
929  /// DensifyOp() = default;
930  ///
931  /// // Processes the root node. Required by the DynamicNodeManager
932  /// bool operator()(RootT&, size_t) const { return true; }
933  ///
934  /// // Processes the internal nodes. Required by the DynamicNodeManager
935  /// template<typename NodeT>
936  /// bool operator()(NodeT& node, size_t idx) const
937  /// {
938  /// // densify child
939  /// for (auto iter = node.cbeginValueAll(); iter; ++iter) {
940  /// const openvdb::Coord ijk = iter.getCoord();
941  /// node.addChild(new typename NodeT::ChildNodeType(iter.getCoord(), NodeT::LEVEL, true));
942  /// }
943  /// // early-exit termination for all non-zero index children
944  /// return idx == 0;
945  /// }
946  /// // Processes the leaf nodes. Required by the DynamicNodeManager
947  /// bool operator()(LeafT&, size_t) const
948  /// {
949  /// return true;
950  /// }
951  /// };// DensifyOp
952  ///
953  /// // usage:
954  /// DensifyOp<FloatTree> op;
955  /// tree::DynamicNodeManager<FloatTree> nodes(tree);
956  /// nodes.foreachTopDown(op);
957  ///
958  /// @endcode
959  template<typename NodeOp>
960  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
961  {
962  mChain.foreachTopDown(op, mRoot, threaded, grainSize);
963  }
964 
965  /// @brief Threaded method that processes nodes with a user supplied functor
966  ///
967  /// @param op user-supplied functor, see examples for interface details.
968  /// @param threaded optional toggle to disable threading, on by default.
969  /// @param grainSize optional parameter to specify the grainsize
970  /// for threading, one by default.
971  ///
972  /// @note There are two key differences to the interface of the
973  /// user-supplied functor to the NodeManager class - (1) the operator()
974  /// method aligns with the LeafManager class in expecting the index of the
975  /// node in a linear array of identical node types, (2) the operator()
976  /// method returns a boolean termination value with true indicating that
977  /// children of this node should be processed, false indicating the
978  /// early-exit termination should occur.
979  ///
980  /// @par Example:
981  /// @code
982  /// // Functor to count nodes in a tree
983  /// template<typename TreeType>
984  /// struct NodeCountOp
985  /// {
986  /// NodeCountOp() : nodeCount(TreeType::DEPTH, 0), totalCount(0)
987  /// {
988  /// }
989  /// NodeCountOp(const NodeCountOp& other, tbb::split) :
990  /// nodeCount(TreeType::DEPTH, 0), totalCount(0)
991  /// {
992  /// }
993  /// void join(const NodeCountOp& other)
994  /// {
995  /// for (size_t i = 0; i < nodeCount.size(); ++i) {
996  /// nodeCount[i] += other.nodeCount[i];
997  /// }
998  /// totalCount += other.totalCount;
999  /// }
1000  /// // do nothing for the root node
1001  /// bool operator()(const typename TreeT::RootNodeType& node, size_t)
1002  /// {
1003  /// return true;
1004  /// }
1005  /// // count the internal and leaf nodes
1006  /// template<typename NodeT>
1007  /// bool operator()(const NodeT& node, size_t)
1008  /// {
1009  /// ++(nodeCount[NodeT::LEVEL]);
1010  /// ++totalCount;
1011  /// return true;
1012  /// }
1013  /// std::vector<openvdb::Index64> nodeCount;
1014  /// openvdb::Index64 totalCount;
1015  /// };
1016  ///
1017  /// // usage:
1018  /// NodeCountOp<FloatTree> op;
1019  /// tree::DynamicNodeManager<FloatTree> nodes(tree);
1020  /// nodes.reduceTopDown(op);
1021  ///
1022  /// @endcode
1023  template<typename NodeOp>
1024  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1025  {
1026  mChain.reduceTopDown(op, mRoot, threaded, grainSize);
1027  }
1028 
1029 protected:
1031  DynamicNodeManagerLink<typename RootNodeType::ChildNodeType, LEVELS-1> mChain;
1032 };// DynamicNodeManager class
1033 
1034 
1035 
1036 ////////////////////////////////////////////
1037 
1038 
1039 /// @private
1040 /// Template specialization of the NodeManager with no caching of nodes
1041 template<typename TreeOrLeafManagerT>
1042 class NodeManager<TreeOrLeafManagerT, 0>
1043 {
1044 public:
1045  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1047  static const Index LEVELS = 0;
1048 
1049  NodeManager(TreeOrLeafManagerT& tree, bool /*serial*/ = false) : mRoot(tree.root()) { }
1050 
1051  NodeManager(const NodeManager&) = delete;
1052 
1053  /// @brief Clear all the cached tree nodes
1054  void clear() {}
1055 
1056  /// @brief Clear and recache all the tree nodes from the
1057  /// tree. This is required if tree nodes have been added or removed.
1058  void rebuild(bool /*serial*/ = false) { }
1059 
1060  /// @brief Return a reference to the root node.
1061  const RootNodeType& root() const { return mRoot; }
1062 
1063  /// @brief Return the total number of cached nodes (excluding the root node)
1064  Index64 nodeCount() const { return 0; }
1065 
1066  Index64 nodeCount(Index) const { return 0; }
1067 
1068  template<typename NodeOp>
1069  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
1070 
1071  template<typename NodeOp>
1072  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
1073 
1074  template<typename NodeOp>
1075  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
1076 
1077  template<typename NodeOp>
1078  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
1079 
1080 protected:
1082 }; // NodeManager<0>
1083 
1084 
1085 ////////////////////////////////////////////
1086 
1087 
1088 /// @private
1089 /// Template specialization of the NodeManager with one level of nodes
1090 template<typename TreeOrLeafManagerT>
1091 class NodeManager<TreeOrLeafManagerT, 1>
1092 {
1093 public:
1094  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1096  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1097  static const Index LEVELS = 1;
1098 
1099  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
1100  : mRoot(tree.root())
1101  {
1102  this->rebuild(serial);
1103  }
1104 
1105  NodeManager(const NodeManager&) = delete;
1106 
1107  /// @brief Clear all the cached tree nodes
1108  void clear() { mList0.clear(); }
1109 
1110  /// @brief Clear and recache all the tree nodes from the
1111  /// tree. This is required if tree nodes have been added or removed.
1112  void rebuild(bool /*serial*/ = false) { mList0.initRootChildren(mRoot); }
1113 
1114  /// @brief Return a reference to the root node.
1115  const RootNodeType& root() const { return mRoot; }
1116 
1117  /// @brief Return the total number of cached nodes (excluding the root node)
1118  Index64 nodeCount() const { return mList0.nodeCount(); }
1119 
1120  /// @brief Return the number of cached nodes at level @a i, where
1121  /// 0 corresponds to the lowest level.
1122  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
1123 
1124  template<typename NodeOp>
1125  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1126  {
1127  mList0.foreach(op, threaded, grainSize);
1128  op(mRoot);
1129  }
1130 
1131  template<typename NodeOp>
1132  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1133  {
1134  op(mRoot);
1135  mList0.foreach(op, threaded, grainSize);
1136  }
1137 
1138  template<typename NodeOp>
1139  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1140  {
1141  mList0.reduce(op, threaded, grainSize);
1142  op(mRoot);
1143  }
1144 
1145  template<typename NodeOp>
1146  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1147  {
1148  op(mRoot);
1149  mList0.reduce(op, threaded, grainSize);
1150  }
1151 
1152 protected:
1153  using NodeT1 = RootNodeType;
1154  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1155  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1156  using ListT0 = NodeList<NodeT0>;
1157 
1158  NodeT1& mRoot;
1159  ListT0 mList0;
1160 }; // NodeManager<1>
1161 
1162 
1163 ////////////////////////////////////////////
1164 
1165 
1166 /// @private
1167 /// Template specialization of the NodeManager with two levels of nodes
1168 template<typename TreeOrLeafManagerT>
1169 class NodeManager<TreeOrLeafManagerT, 2>
1170 {
1171 public:
1172  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1174  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1175  static const Index LEVELS = 2;
1176 
1177  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1178  {
1179  this->rebuild(serial);
1180  }
1181 
1182  NodeManager(const NodeManager&) = delete;
1183 
1184  /// @brief Clear all the cached tree nodes
1185  void clear() { mList0.clear(); mList1.clear(); }
1186 
1187  /// @brief Clear and recache all the tree nodes from the
1188  /// tree. This is required if tree nodes have been added or removed.
1189  void rebuild(bool serial = false)
1190  {
1191  mList1.initRootChildren(mRoot);
1192  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1193  }
1194 
1195  /// @brief Return a reference to the root node.
1196  const RootNodeType& root() const { return mRoot; }
1197 
1198  /// @brief Return the total number of cached nodes (excluding the root node)
1199  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
1200 
1201  /// @brief Return the number of cached nodes at level @a i, where
1202  /// 0 corresponds to the lowest level.
1203  Index64 nodeCount(Index i) const
1204  {
1205  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1206  }
1207 
1208  template<typename NodeOp>
1209  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1210  {
1211  mList0.foreach(op, threaded, grainSize);
1212  mList1.foreach(op, threaded, grainSize);
1213  op(mRoot);
1214  }
1215 
1216  template<typename NodeOp>
1217  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1218  {
1219  op(mRoot);
1220  mList1.foreach(op, threaded, grainSize);
1221  mList0.foreach(op, threaded, grainSize);
1222  }
1223 
1224  template<typename NodeOp>
1225  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1226  {
1227  mList0.reduce(op, threaded, grainSize);
1228  mList1.reduce(op, threaded, grainSize);
1229  op(mRoot);
1230  }
1231 
1232  template<typename NodeOp>
1233  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1234  {
1235  op(mRoot);
1236  mList1.reduce(op, threaded, grainSize);
1237  mList0.reduce(op, threaded, grainSize);
1238  }
1239 
1240 protected:
1241  using NodeT2 = RootNodeType;
1242  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1243  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1244  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1245  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1246 
1247  using ListT1 = NodeList<NodeT1>; // upper level
1248  using ListT0 = NodeList<NodeT0>; // lower level
1249 
1250  NodeT2& mRoot;
1251  ListT1 mList1;
1252  ListT0 mList0;
1253 }; // NodeManager<2>
1254 
1255 
1256 ////////////////////////////////////////////
1257 
1258 
1259 /// @private
1260 /// Template specialization of the NodeManager with three levels of nodes
1261 template<typename TreeOrLeafManagerT>
1262 class NodeManager<TreeOrLeafManagerT, 3>
1263 {
1264 public:
1265  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1267  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1268  static const Index LEVELS = 3;
1269 
1270  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1271  {
1272  this->rebuild(serial);
1273  }
1274 
1275  NodeManager(const NodeManager&) = delete;
1276 
1277  /// @brief Clear all the cached tree nodes
1278  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1279 
1280  /// @brief Clear and recache all the tree nodes from the
1281  /// tree. This is required if tree nodes have been added or removed.
1282  void rebuild(bool serial = false)
1283  {
1284  mList2.initRootChildren(mRoot);
1285  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1286  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1287  }
1288 
1289  /// @brief Return a reference to the root node.
1290  const RootNodeType& root() const { return mRoot; }
1291 
1292  /// @brief Return the total number of cached nodes (excluding the root node)
1293  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1294 
1295  /// @brief Return the number of cached nodes at level @a i, where
1296  /// 0 corresponds to the lowest level.
1297  Index64 nodeCount(Index i) const
1298  {
1299  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1300  : i==2 ? mList2.nodeCount() : 0;
1301  }
1302 
1303  template<typename NodeOp>
1304  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1305  {
1306  mList0.foreach(op, threaded, grainSize);
1307  mList1.foreach(op, threaded, grainSize);
1308  mList2.foreach(op, threaded, grainSize);
1309  op(mRoot);
1310  }
1311 
1312  template<typename NodeOp>
1313  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1314  {
1315  op(mRoot);
1316  mList2.foreach(op, threaded, grainSize);
1317  mList1.foreach(op, threaded, grainSize);
1318  mList0.foreach(op, threaded, grainSize);
1319  }
1320 
1321  template<typename NodeOp>
1322  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1323  {
1324  mList0.reduce(op, threaded, grainSize);
1325  mList1.reduce(op, threaded, grainSize);
1326  mList2.reduce(op, threaded, grainSize);
1327  op(mRoot);
1328  }
1329 
1330  template<typename NodeOp>
1331  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1332  {
1333  op(mRoot);
1334  mList2.reduce(op, threaded, grainSize);
1335  mList1.reduce(op, threaded, grainSize);
1336  mList0.reduce(op, threaded, grainSize);
1337  }
1338 
1339 protected:
1340  using NodeT3 = RootNodeType;
1341  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1342  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1343  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1344  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1345  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1346  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1347 
1348  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1349  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1350  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1351 
1352  NodeT3& mRoot;
1353  ListT2 mList2;
1354  ListT1 mList1;
1355  ListT0 mList0;
1356 }; // NodeManager<3>
1357 
1358 
1359 ////////////////////////////////////////////
1360 
1361 
1362 /// @private
1363 /// Template specialization of the NodeManager with four levels of nodes
1364 template<typename TreeOrLeafManagerT>
1365 class NodeManager<TreeOrLeafManagerT, 4>
1366 {
1367 public:
1368  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1370  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1371  static const Index LEVELS = 4;
1372 
1373  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1374  {
1375  this->rebuild(serial);
1376  }
1377 
1378  NodeManager(const NodeManager&) = delete; // disallow copy-construction
1379 
1380  /// @brief Clear all the cached tree nodes
1381  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1382 
1383  /// @brief Clear and recache all the tree nodes from the
1384  /// tree. This is required if tree nodes have been added or removed.
1385  void rebuild(bool serial = false)
1386  {
1387  mList3.initRootChildren(mRoot);
1388  mList2.initNodeChildren(mList3, NodeFilter(), serial);
1389  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1390  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1391  }
1392 
1393  /// @brief Return a reference to the root node.
1394  const RootNodeType& root() const { return mRoot; }
1395 
1396  /// @brief Return the total number of cached nodes (excluding the root node)
1397  Index64 nodeCount() const
1398  {
1399  return mList0.nodeCount() + mList1.nodeCount()
1400  + mList2.nodeCount() + mList3.nodeCount();
1401  }
1402 
1403  /// @brief Return the number of cached nodes at level @a i, where
1404  /// 0 corresponds to the lowest level.
1405  Index64 nodeCount(Index i) const
1406  {
1407  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1408  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1409  }
1410 
1411  template<typename NodeOp>
1412  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1413  {
1414  mList0.foreach(op, threaded, grainSize);
1415  mList1.foreach(op, threaded, grainSize);
1416  mList2.foreach(op, threaded, grainSize);
1417  mList3.foreach(op, threaded, grainSize);
1418  op(mRoot);
1419  }
1420 
1421  template<typename NodeOp>
1422  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1423  {
1424  op(mRoot);
1425  mList3.foreach(op, threaded, grainSize);
1426  mList2.foreach(op, threaded, grainSize);
1427  mList1.foreach(op, threaded, grainSize);
1428  mList0.foreach(op, threaded, grainSize);
1429  }
1430 
1431  template<typename NodeOp>
1432  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1433  {
1434  mList0.reduce(op, threaded, grainSize);
1435  mList1.reduce(op, threaded, grainSize);
1436  mList2.reduce(op, threaded, grainSize);
1437  mList3.reduce(op, threaded, grainSize);
1438  op(mRoot);
1439  }
1440 
1441  template<typename NodeOp>
1442  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1443  {
1444  op(mRoot);
1445  mList3.reduce(op, threaded, grainSize);
1446  mList2.reduce(op, threaded, grainSize);
1447  mList1.reduce(op, threaded, grainSize);
1448  mList0.reduce(op, threaded, grainSize);
1449  }
1450 
1451 protected:
1452  using NodeT4 = RootNodeType;
1453  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1454  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1455  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1456  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1457  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1458  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1459  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1460  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1461 
1462  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1463  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1464  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1465  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1466 
1467  NodeT4& mRoot;
1468  ListT3 mList3;
1469  ListT2 mList2;
1470  ListT1 mList1;
1471  ListT0 mList0;
1472 }; // NodeManager<4>
1473 
1474 
1475 ////////////////////////////////////////////
1476 
1477 
1478 /// @private
1479 /// Template specialization of the DynamicNodeManager with one level of nodes
1480 template<typename TreeOrLeafManagerT>
1481 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1482 {
1483 public:
1484  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1485  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1486  static const Index LEVELS = 1;
1487 
1488  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1489 
1490  DynamicNodeManager(const DynamicNodeManager&) = delete;
1491 
1492  /// @brief Return a reference to the root node.
1493  const RootNodeType& root() const { return mRoot; }
1494 
1495  template<typename NodeOp>
1496  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1497  {
1498  // root
1499  if (!op(mRoot, /*index=*/0)) return;
1500  // list0
1501  if (!mList0.initRootChildren(mRoot)) return;
1502  ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1503  mList0.foreachWithIndex(nodeOp, threaded, grainSize);
1504  }
1505 
1506  template<typename NodeOp>
1507  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1508  {
1509  // root
1510  if (!op(mRoot, /*index=*/0)) return;
1511  // list0
1512  if (!mList0.initRootChildren(mRoot)) return;
1513  ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1514  mList0.reduceWithIndex(nodeOp, threaded, grainSize);
1515  }
1516 
1517 protected:
1518  using NodeT1 = RootNodeType;
1519  using NodeT0 = typename NodeT1::ChildNodeType;
1520 
1521  using ListT0 = NodeList<NodeT0>;
1522 
1523  NodeT1& mRoot;
1524  ListT0 mList0;
1525 };// DynamicNodeManager<1> class
1526 
1527 
1528 ////////////////////////////////////////////
1529 
1530 
1531 /// @private
1532 /// Template specialization of the DynamicNodeManager with two levels of nodes
1533 template<typename TreeOrLeafManagerT>
1534 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1535 {
1536 public:
1537  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1538  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1539  static const Index LEVELS = 2;
1540 
1541  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1542 
1543  DynamicNodeManager(const DynamicNodeManager&) = delete;
1544 
1545  /// @brief Return a reference to the root node.
1546  const RootNodeType& root() const { return mRoot; }
1547 
1548  template<typename NodeOp>
1549  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1550  {
1551  // root
1552  if (!op(mRoot, /*index=*/0)) return;
1553  // list1
1554  if (!mList1.initRootChildren(mRoot)) return;
1555  ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1556  mList1.foreachWithIndex(nodeOp, threaded, grainSize);
1557  // list0
1558  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1559  mList0.foreachWithIndex(op, threaded, grainSize);
1560  }
1561 
1562  template<typename NodeOp>
1563  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1564  {
1565  // root
1566  if (!op(mRoot, /*index=*/0)) return;
1567  // list1
1568  if (!mList1.initRootChildren(mRoot)) return;
1569  ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1570  mList1.reduceWithIndex(nodeOp, threaded, grainSize);
1571  // list0
1572  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1573  mList0.reduceWithIndex(op, threaded, grainSize);
1574  }
1575 
1576 protected:
1577  using NodeT2 = RootNodeType;
1578  using NodeT1 = typename NodeT2::ChildNodeType; // upper level
1579  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1580 
1581  using ListT1 = NodeList<NodeT1>; // upper level of internal nodes
1582  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1583 
1584  NodeT2& mRoot;
1585  ListT1 mList1;
1586  ListT0 mList0;
1587 };// DynamicNodeManager<2> class
1588 
1589 
1590 ////////////////////////////////////////////
1591 
1592 
1593 /// @private
1594 /// Template specialization of the DynamicNodeManager with three levels of nodes
1595 template<typename TreeOrLeafManagerT>
1596 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1597 {
1598 public:
1599  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1600  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1601  static const Index LEVELS = 3;
1602 
1603  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1604 
1605  DynamicNodeManager(const DynamicNodeManager&) = delete;
1606 
1607  /// @brief Return a reference to the root node.
1608  const RootNodeType& root() const { return mRoot; }
1609 
1610  template<typename NodeOp>
1611  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1612  {
1613  // root
1614  if (!op(mRoot, /*index=*/0)) return;
1615  // list2
1616  if (!mList2.initRootChildren(mRoot)) return;
1617  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1618  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1619  // list1
1620  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1621  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1622  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1623  // list0
1624  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1625  mList0.foreachWithIndex(op, threaded, grainSize);
1626  }
1627 
1628  template<typename NodeOp>
1629  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1630  {
1631  // root
1632  if (!op(mRoot, /*index=*/0)) return;
1633  // list2
1634  if (!mList2.initRootChildren(mRoot)) return;
1635  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1636  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1637  // list1
1638  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1639  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1640  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1641  // list0
1642  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1643  mList0.reduceWithIndex(op, threaded, grainSize);
1644  }
1645 
1646 protected:
1647  using NodeT3 = RootNodeType;
1648  using NodeT2 = typename NodeT3::ChildNodeType; // upper level
1649  using NodeT1 = typename NodeT2::ChildNodeType; // mid level
1650  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1651 
1652  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1653  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1654  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1655 
1656  NodeT3& mRoot;
1657  ListT2 mList2;
1658  ListT1 mList1;
1659  ListT0 mList0;
1660 };// DynamicNodeManager<3> class
1661 
1662 
1663 ////////////////////////////////////////////
1664 
1665 
1666 /// @private
1667 /// Template specialization of the DynamicNodeManager with four levels of nodes
1668 template<typename TreeOrLeafManagerT>
1669 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1670 {
1671 public:
1672  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1673  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1674  static const Index LEVELS = 4;
1675 
1676  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1677 
1678  DynamicNodeManager(const DynamicNodeManager&) = delete;
1679 
1680  /// @brief Return a reference to the root node.
1681  const RootNodeType& root() const { return mRoot; }
1682 
1683  template<typename NodeOp>
1684  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1685  {
1686  // root
1687  if (!op(mRoot, /*index=*/0)) return;
1688  // list3
1689  if (!mList3.initRootChildren(mRoot)) return;
1690  ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1691  mList3.foreachWithIndex(nodeOp3, threaded, grainSize);
1692  // list2
1693  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1694  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1695  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1696  // list1
1697  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1698  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1699  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1700  // list0
1701  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1702  mList0.foreachWithIndex(op, threaded, grainSize);
1703  }
1704 
1705  template<typename NodeOp>
1706  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1707  {
1708  // root
1709  if (!op(mRoot, /*index=*/0)) return;
1710  // list3
1711  if (!mList3.initRootChildren(mRoot)) return;
1712  ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1713  mList3.reduceWithIndex(nodeOp3, threaded, grainSize);
1714  // list2
1715  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1716  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1717  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1718  // list1
1719  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1720  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1721  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1722  // list0
1723  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1724  mList0.reduceWithIndex(op, threaded, grainSize);
1725  }
1726 
1727 protected:
1728  using NodeT4 = RootNodeType;
1729  using NodeT3 = typename NodeT4::ChildNodeType; // upper level
1730  using NodeT2 = typename NodeT3::ChildNodeType; // upper mid level
1731  using NodeT1 = typename NodeT2::ChildNodeType; // lower mid level
1732  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1733 
1734  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1735  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1736  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1737  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1738 
1739  NodeT4& mRoot;
1740  ListT3 mList3;
1741  ListT2 mList2;
1742  ListT1 mList1;
1743  ListT0 mList0;
1744 };// DynamicNodeManager<4> class
1745 
1746 
1747 } // namespace tree
1748 } // namespace OPENVDB_VERSION_NAME
1749 } // namespace openvdb
1750 
1751 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:191
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:222
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:705
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
Definition: parallel.h:153
GLenum GLint * range
Definition: glew.h:3500
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:892
GLsizeiptr size
Definition: glew.h:1681
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:561
GLuint GLenum GLenum transform
Definition: glew.h:14742
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:220
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:960
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:1024
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:167
ForeachFilterOp(const OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:726
NodeManager(TreeOrLeafManagerT &tree, bool serial=false)
Definition: NodeManager.h:542
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:551
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:54
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:539
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays, one for each level of the tree.
Definition: NodeManager.h:30
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:275
void OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
void foreachWithIndex(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:284
void rebuild(bool serial=false)
Clear and recache all the tree nodes from the tree. This is required if tree nodes have been added or...
Definition: NodeManager.h:555
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:772
void foreachBottomUp(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:624
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:538
*But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:639
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:224
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:736
typename std::remove_const< ToType >::type Type
Definition: Types.h:299
GLuint GLuint end
Definition: glew.h:1253
ReduceFilterOp(OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:757
GLsizei n
Definition: glew.h:4040
void join(const ReduceFilterOp &other)
Definition: NodeManager.h:777
HUSD_API bool eval(VtValue &val, T &ret_val)
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:565
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:558
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:537
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:536
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:884
bool initNodeChildren(ParentsT &parents, const NodeFilterT &nodeFilter=NodeFilterT(), bool serial=false)
Definition: NodeManager.h:105
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:698
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
DynamicNodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:1031
std::unique_ptr< NodeT *[]> mNodePtrs
Definition: NodeManager.h:389
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:231
arg_join< It, char > join(It begin, It end, string_view sep)
Definition: format.h:3326
void reduceWithIndex(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:292
ReduceFilterOp(const ReduceFilterOp &other, tbb::split)
Definition: NodeManager.h:766
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:113
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:631
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:262
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:227
NodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:714