OpenVDB  8.1.1
NodeManager.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
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 
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 
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  }
88  mNodeCount = nodeCount;
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());
118  tbb::parallel_for(
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  }
151  mNodeCount = nodeCount;
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 {
167  tbb::parallel_for(
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 
194  NodeRange(NodeRange& r, tbb::split):
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;
218  Iterator& operator++() { ++mPos; return *this; }
220  NodeT& operator*() const { return mRange.mNodeList(mPos); }
222  NodeT* operator->() const { return &(this->operator*()); }
224  size_t pos() const { return mPos; }
225  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
227  bool test() const { return mPos < mRange.mEnd; }
229  operator bool() const { return this->test(); }
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 
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 
395 
396 
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 
468 
469 
473 template<typename NodeT>
474 class NodeManagerLink<NodeT, 0>
475 {
476 public:
477  NodeManagerLink() = default;
478 
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 
522 
523 
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 
551  void clear() { mChain.clear(); }
552 
555  void rebuild(bool serial = false) { mChain.initRootChildren(mRoot, serial); }
556 
558  const RootNodeType& root() const { return mRoot; }
559 
561  Index64 nodeCount() const { return mChain.nodeCount(); }
562 
565  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
566 
568  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 
638 
640  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  }
711 
712 protected:
715 };// NodeManager class
716 
717 
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 
766  ReduceFilterOp(const ReduceFilterOp& other, tbb::split)
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 
801 template<typename NodeT, Index LEVEL>
803 {
804 public:
805  using NonConstChildNodeType = typename NodeT::ChildNodeType;
807 
808  DynamicNodeManagerLink() = default;
809 
810  template<typename NodeOpT, typename RootT>
811  void foreachTopDown(const NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
812  {
813  if (!op(root, /*index=*/0)) return;
814  if (!mList.initRootChildren(root)) return;
815  ForeachFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
816  mList.foreachWithIndex(filterOp, threaded, grainSize);
817  mNext.foreachTopDownRecurse(filterOp, mList, threaded, grainSize);
818  }
819 
820  template<typename FilterOpT, typename ParentT>
821  void foreachTopDownRecurse(const FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
822  {
823  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
824  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
825  mList.foreachWithIndex(childFilterOp, threaded, grainSize);
826  mNext.foreachTopDownRecurse(childFilterOp, mList, threaded, grainSize);
827  }
828 
829  template<typename NodeOpT, typename RootT>
830  void reduceTopDown(NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
831  {
832  if (!op(root, /*index=*/0)) return;
833  if (!mList.initRootChildren(root)) return;
834  ReduceFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
835  mList.reduceWithIndex(filterOp, threaded, grainSize);
836  mNext.reduceTopDownRecurse(filterOp, mList, threaded, grainSize);
837  }
838 
839  template<typename FilterOpT, typename ParentT>
840  void reduceTopDownRecurse(FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
841  {
842  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
843  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
844  mList.reduceWithIndex(childFilterOp, threaded, grainSize);
845  mNext.reduceTopDownRecurse(childFilterOp, mList, threaded, grainSize);
846  }
847 
848 protected:
851 };// DynamicNodeManagerLink class
852 
853 
857 template<typename NodeT>
858 class DynamicNodeManagerLink<NodeT, 0>
859 {
860 public:
861  DynamicNodeManagerLink() = default;
862 
863  template<typename NodeFilterOp, typename ParentT>
864  void foreachTopDownRecurse(const NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
865  {
866  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
867  mList.foreachWithIndex(nodeFilterOp.op(), threaded, grainSize);
868  }
869 
870  template<typename NodeFilterOp, typename ParentT>
871  void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
872  {
873  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
874  mList.reduceWithIndex(nodeFilterOp.op(), threaded, grainSize);
875  }
876 
877 protected:
878  NodeList<NodeT> mList;
879 };// DynamicNodeManagerLink class
880 
881 
882 template<typename TreeOrLeafManagerT, Index _LEVELS>
883 class DynamicNodeManager
884 {
885 public:
886  static const Index LEVELS = _LEVELS;
887  static_assert(LEVELS > 0,
888  "expected instantiation of template specialization"); // see specialization below
889  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
891  using NonConstChildNodeType = typename RootNodeType::ChildNodeType;
893  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
894 
895  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
896 
897  DynamicNodeManager(const DynamicNodeManager&) = delete;
898 
900  const NonConstRootNodeType& root() const { return mRoot; }
901 
967  template<typename NodeOp>
968  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
969  {
970  mChain.foreachTopDown(op, mRoot, threaded, grainSize);
971  }
972 
1031  template<typename NodeOp>
1032  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1033  {
1034  mChain.reduceTopDown(op, mRoot, threaded, grainSize);
1035  }
1036 
1037 protected:
1040 };// DynamicNodeManager class
1041 
1042 
1043 
1045 
1046 
1049 template<typename TreeOrLeafManagerT>
1050 class NodeManager<TreeOrLeafManagerT, 0>
1051 {
1052 public:
1053  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1055  static const Index LEVELS = 0;
1056 
1057  NodeManager(TreeOrLeafManagerT& tree, bool /*serial*/ = false) : mRoot(tree.root()) { }
1058 
1059  NodeManager(const NodeManager&) = delete;
1060 
1062  void clear() {}
1063 
1066  void rebuild(bool /*serial*/ = false) { }
1067 
1069  const RootNodeType& root() const { return mRoot; }
1070 
1072  Index64 nodeCount() const { return 0; }
1073 
1074  Index64 nodeCount(Index) const { return 0; }
1075 
1076  template<typename NodeOp>
1077  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
1078 
1079  template<typename NodeOp>
1080  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
1081 
1082  template<typename NodeOp>
1083  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
1084 
1085  template<typename NodeOp>
1086  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
1087 
1088 protected:
1089  RootNodeType& mRoot;
1090 }; // NodeManager<0>
1091 
1092 
1094 
1095 
1098 template<typename TreeOrLeafManagerT>
1099 class NodeManager<TreeOrLeafManagerT, 1>
1100 {
1101 public:
1102  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1104  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1105  static const Index LEVELS = 1;
1106 
1107  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
1108  : mRoot(tree.root())
1109  {
1110  this->rebuild(serial);
1111  }
1112 
1113  NodeManager(const NodeManager&) = delete;
1114 
1116  void clear() { mList0.clear(); }
1117 
1120  void rebuild(bool /*serial*/ = false) { mList0.initRootChildren(mRoot); }
1121 
1123  const RootNodeType& root() const { return mRoot; }
1124 
1126  Index64 nodeCount() const { return mList0.nodeCount(); }
1127 
1130  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
1131 
1132  template<typename NodeOp>
1133  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1134  {
1135  mList0.foreach(op, threaded, grainSize);
1136  op(mRoot);
1137  }
1138 
1139  template<typename NodeOp>
1140  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1141  {
1142  op(mRoot);
1143  mList0.foreach(op, threaded, grainSize);
1144  }
1145 
1146  template<typename NodeOp>
1147  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1148  {
1149  mList0.reduce(op, threaded, grainSize);
1150  op(mRoot);
1151  }
1152 
1153  template<typename NodeOp>
1154  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1155  {
1156  op(mRoot);
1157  mList0.reduce(op, threaded, grainSize);
1158  }
1159 
1160 protected:
1161  using NodeT1 = RootNodeType;
1162  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1163  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1164  using ListT0 = NodeList<NodeT0>;
1165 
1166  NodeT1& mRoot;
1167  ListT0 mList0;
1168 }; // NodeManager<1>
1169 
1170 
1172 
1173 
1176 template<typename TreeOrLeafManagerT>
1177 class NodeManager<TreeOrLeafManagerT, 2>
1178 {
1179 public:
1180  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1182  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1183  static const Index LEVELS = 2;
1184 
1185  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1186  {
1187  this->rebuild(serial);
1188  }
1189 
1190  NodeManager(const NodeManager&) = delete;
1191 
1193  void clear() { mList0.clear(); mList1.clear(); }
1194 
1197  void rebuild(bool serial = false)
1198  {
1199  mList1.initRootChildren(mRoot);
1200  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1201  }
1202 
1204  const RootNodeType& root() const { return mRoot; }
1205 
1207  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
1208 
1211  Index64 nodeCount(Index i) const
1212  {
1213  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1214  }
1215 
1216  template<typename NodeOp>
1217  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1218  {
1219  mList0.foreach(op, threaded, grainSize);
1220  mList1.foreach(op, threaded, grainSize);
1221  op(mRoot);
1222  }
1223 
1224  template<typename NodeOp>
1225  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1226  {
1227  op(mRoot);
1228  mList1.foreach(op, threaded, grainSize);
1229  mList0.foreach(op, threaded, grainSize);
1230  }
1231 
1232  template<typename NodeOp>
1233  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1234  {
1235  mList0.reduce(op, threaded, grainSize);
1236  mList1.reduce(op, threaded, grainSize);
1237  op(mRoot);
1238  }
1239 
1240  template<typename NodeOp>
1241  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1242  {
1243  op(mRoot);
1244  mList1.reduce(op, threaded, grainSize);
1245  mList0.reduce(op, threaded, grainSize);
1246  }
1247 
1248 protected:
1249  using NodeT2 = RootNodeType;
1250  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1251  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1252  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1253  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1254 
1255  using ListT1 = NodeList<NodeT1>; // upper level
1256  using ListT0 = NodeList<NodeT0>; // lower level
1257 
1258  NodeT2& mRoot;
1259  ListT1 mList1;
1260  ListT0 mList0;
1261 }; // NodeManager<2>
1262 
1263 
1265 
1266 
1269 template<typename TreeOrLeafManagerT>
1270 class NodeManager<TreeOrLeafManagerT, 3>
1271 {
1272 public:
1273  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1275  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1276  static const Index LEVELS = 3;
1277 
1278  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1279  {
1280  this->rebuild(serial);
1281  }
1282 
1283  NodeManager(const NodeManager&) = delete;
1284 
1286  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1287 
1290  void rebuild(bool serial = false)
1291  {
1292  mList2.initRootChildren(mRoot);
1293  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1294  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1295  }
1296 
1298  const RootNodeType& root() const { return mRoot; }
1299 
1301  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1302 
1305  Index64 nodeCount(Index i) const
1306  {
1307  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1308  : i==2 ? mList2.nodeCount() : 0;
1309  }
1310 
1311  template<typename NodeOp>
1312  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1313  {
1314  mList0.foreach(op, threaded, grainSize);
1315  mList1.foreach(op, threaded, grainSize);
1316  mList2.foreach(op, threaded, grainSize);
1317  op(mRoot);
1318  }
1319 
1320  template<typename NodeOp>
1321  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1322  {
1323  op(mRoot);
1324  mList2.foreach(op, threaded, grainSize);
1325  mList1.foreach(op, threaded, grainSize);
1326  mList0.foreach(op, threaded, grainSize);
1327  }
1328 
1329  template<typename NodeOp>
1330  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1331  {
1332  mList0.reduce(op, threaded, grainSize);
1333  mList1.reduce(op, threaded, grainSize);
1334  mList2.reduce(op, threaded, grainSize);
1335  op(mRoot);
1336  }
1337 
1338  template<typename NodeOp>
1339  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1340  {
1341  op(mRoot);
1342  mList2.reduce(op, threaded, grainSize);
1343  mList1.reduce(op, threaded, grainSize);
1344  mList0.reduce(op, threaded, grainSize);
1345  }
1346 
1347 protected:
1348  using NodeT3 = RootNodeType;
1349  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1350  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1351  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1352  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1353  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1354  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1355 
1356  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1357  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1358  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1359 
1360  NodeT3& mRoot;
1361  ListT2 mList2;
1362  ListT1 mList1;
1363  ListT0 mList0;
1364 }; // NodeManager<3>
1365 
1366 
1368 
1369 
1372 template<typename TreeOrLeafManagerT>
1373 class NodeManager<TreeOrLeafManagerT, 4>
1374 {
1375 public:
1376  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1378  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1379  static const Index LEVELS = 4;
1380 
1381  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1382  {
1383  this->rebuild(serial);
1384  }
1385 
1386  NodeManager(const NodeManager&) = delete; // disallow copy-construction
1387 
1389  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1390 
1393  void rebuild(bool serial = false)
1394  {
1395  mList3.initRootChildren(mRoot);
1396  mList2.initNodeChildren(mList3, NodeFilter(), serial);
1397  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1398  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1399  }
1400 
1402  const RootNodeType& root() const { return mRoot; }
1403 
1405  Index64 nodeCount() const
1406  {
1407  return mList0.nodeCount() + mList1.nodeCount()
1408  + mList2.nodeCount() + mList3.nodeCount();
1409  }
1410 
1413  Index64 nodeCount(Index i) const
1414  {
1415  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1416  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1417  }
1418 
1419  template<typename NodeOp>
1420  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1421  {
1422  mList0.foreach(op, threaded, grainSize);
1423  mList1.foreach(op, threaded, grainSize);
1424  mList2.foreach(op, threaded, grainSize);
1425  mList3.foreach(op, threaded, grainSize);
1426  op(mRoot);
1427  }
1428 
1429  template<typename NodeOp>
1430  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1431  {
1432  op(mRoot);
1433  mList3.foreach(op, threaded, grainSize);
1434  mList2.foreach(op, threaded, grainSize);
1435  mList1.foreach(op, threaded, grainSize);
1436  mList0.foreach(op, threaded, grainSize);
1437  }
1438 
1439  template<typename NodeOp>
1440  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1441  {
1442  mList0.reduce(op, threaded, grainSize);
1443  mList1.reduce(op, threaded, grainSize);
1444  mList2.reduce(op, threaded, grainSize);
1445  mList3.reduce(op, threaded, grainSize);
1446  op(mRoot);
1447  }
1448 
1449  template<typename NodeOp>
1450  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1451  {
1452  op(mRoot);
1453  mList3.reduce(op, threaded, grainSize);
1454  mList2.reduce(op, threaded, grainSize);
1455  mList1.reduce(op, threaded, grainSize);
1456  mList0.reduce(op, threaded, grainSize);
1457  }
1458 
1459 protected:
1460  using NodeT4 = RootNodeType;
1461  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1462  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1463  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1464  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1465  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1466  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1467  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1468  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1469 
1470  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1471  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1472  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1473  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1474 
1475  NodeT4& mRoot;
1476  ListT3 mList3;
1477  ListT2 mList2;
1478  ListT1 mList1;
1479  ListT0 mList0;
1480 }; // NodeManager<4>
1481 
1482 
1484 
1485 
1488 template<typename TreeOrLeafManagerT>
1489 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1490 {
1491 public:
1492  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1494  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1495  static const Index LEVELS = 1;
1496 
1497  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1498 
1499  DynamicNodeManager(const DynamicNodeManager&) = delete;
1500 
1502  const RootNodeType& root() const { return mRoot; }
1503 
1504  template<typename NodeOp>
1505  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1506  {
1507  // root
1508  if (!op(mRoot, /*index=*/0)) return;
1509  // list0
1510  if (!mList0.initRootChildren(mRoot)) return;
1511  ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1512  mList0.foreachWithIndex(nodeOp, threaded, grainSize);
1513  }
1514 
1515  template<typename NodeOp>
1516  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1517  {
1518  // root
1519  if (!op(mRoot, /*index=*/0)) return;
1520  // list0
1521  if (!mList0.initRootChildren(mRoot)) return;
1522  ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1523  mList0.reduceWithIndex(nodeOp, threaded, grainSize);
1524  }
1525 
1526 protected:
1527  using NodeT1 = RootNodeType;
1528  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1529  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1530  using ListT0 = NodeList<NodeT0>;
1531 
1532  NodeT1& mRoot;
1533  ListT0 mList0;
1534 };// DynamicNodeManager<1> class
1535 
1536 
1538 
1539 
1542 template<typename TreeOrLeafManagerT>
1543 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1544 {
1545 public:
1546  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1548  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1549  static const Index LEVELS = 2;
1550 
1551  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1552 
1553  DynamicNodeManager(const DynamicNodeManager&) = delete;
1554 
1556  const RootNodeType& root() const { return mRoot; }
1557 
1558  template<typename NodeOp>
1559  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1560  {
1561  // root
1562  if (!op(mRoot, /*index=*/0)) return;
1563  // list1
1564  if (!mList1.initRootChildren(mRoot)) return;
1565  ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1566  mList1.foreachWithIndex(nodeOp, threaded, grainSize);
1567  // list0
1568  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1569  mList0.foreachWithIndex(op, threaded, grainSize);
1570  }
1571 
1572  template<typename NodeOp>
1573  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1574  {
1575  // root
1576  if (!op(mRoot, /*index=*/0)) return;
1577  // list1
1578  if (!mList1.initRootChildren(mRoot)) return;
1579  ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1580  mList1.reduceWithIndex(nodeOp, threaded, grainSize);
1581  // list0
1582  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1583  mList0.reduceWithIndex(op, threaded, grainSize);
1584  }
1585 
1586 protected:
1587  using NodeT2 = RootNodeType;
1588  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1589  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1590  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1591  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1592 
1593  using ListT1 = NodeList<NodeT1>; // upper level
1594  using ListT0 = NodeList<NodeT0>; // lower level
1595 
1596  NodeT2& mRoot;
1597  ListT1 mList1;
1598  ListT0 mList0;
1599 };// DynamicNodeManager<2> class
1600 
1601 
1603 
1604 
1607 template<typename TreeOrLeafManagerT>
1608 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1609 {
1610 public:
1611  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1613  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1614  static const Index LEVELS = 3;
1615 
1616  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1617 
1618  DynamicNodeManager(const DynamicNodeManager&) = delete;
1619 
1621  const RootNodeType& root() const { return mRoot; }
1622 
1623  template<typename NodeOp>
1624  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1625  {
1626  // root
1627  if (!op(mRoot, /*index=*/0)) return;
1628  // list2
1629  if (!mList2.initRootChildren(mRoot)) return;
1630  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1631  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1632  // list1
1633  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1634  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1635  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1636  // list0
1637  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1638  mList0.foreachWithIndex(op, threaded, grainSize);
1639  }
1640 
1641  template<typename NodeOp>
1642  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1643  {
1644  // root
1645  if (!op(mRoot, /*index=*/0)) return;
1646  // list2
1647  if (!mList2.initRootChildren(mRoot)) return;
1648  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1649  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1650  // list1
1651  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1652  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1653  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1654  // list0
1655  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1656  mList0.reduceWithIndex(op, threaded, grainSize);
1657  }
1658 
1659 protected:
1660  using NodeT3 = RootNodeType;
1661  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1662  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1663  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1664  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1665  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1666  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1667 
1668  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1669  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1670  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1671 
1672  NodeT3& mRoot;
1673  ListT2 mList2;
1674  ListT1 mList1;
1675  ListT0 mList0;
1676 };// DynamicNodeManager<3> class
1677 
1678 
1680 
1681 
1684 template<typename TreeOrLeafManagerT>
1685 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1686 {
1687 public:
1688  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1690  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1691  static const Index LEVELS = 4;
1692 
1693  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1694 
1695  DynamicNodeManager(const DynamicNodeManager&) = delete;
1696 
1698  const RootNodeType& root() const { return mRoot; }
1699 
1700  template<typename NodeOp>
1701  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1702  {
1703  // root
1704  if (!op(mRoot, /*index=*/0)) return;
1705  // list3
1706  if (!mList3.initRootChildren(mRoot)) return;
1707  ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1708  mList3.foreachWithIndex(nodeOp3, threaded, grainSize);
1709  // list2
1710  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1711  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1712  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1713  // list1
1714  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1715  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1716  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1717  // list0
1718  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1719  mList0.foreachWithIndex(op, threaded, grainSize);
1720  }
1721 
1722  template<typename NodeOp>
1723  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1724  {
1725  // root
1726  if (!op(mRoot, /*index=*/0)) return;
1727  // list3
1728  if (!mList3.initRootChildren(mRoot)) return;
1729  ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1730  mList3.reduceWithIndex(nodeOp3, threaded, grainSize);
1731  // list2
1732  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1733  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1734  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1735  // list1
1736  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1737  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1738  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1739  // list0
1740  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1741  mList0.reduceWithIndex(op, threaded, grainSize);
1742  }
1743 
1744 protected:
1745  using NodeT4 = RootNodeType;
1746  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1747  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1748  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1749  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1750  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1751  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1752  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1753  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1754 
1755  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1756  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1757  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1758  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1759 
1760  NodeT4& mRoot;
1761  ListT3 mList3;
1762  ListT2 mList2;
1763  ListT1 mList1;
1764  ListT0 mList0;
1765 };// DynamicNodeManager<4> class
1766 
1767 
1768 } // namespace tree
1769 } // namespace OPENVDB_VERSION_NAME
1770 } // namespace openvdb
1771 
1772 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
ForeachFilterOp(const OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:726
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:968
const OpT & op() const
Definition: NodeManager.h:743
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:551
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:1032
NodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:714
bool isValid() const
Definition: NodeManager.h:225
void join(const ReduceFilterOp &other)
Definition: NodeManager.h:777
ReduceFilterOp(OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:757
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:262
Iterator end() const
Definition: NodeManager.h:246
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
Definition: NodeManager.h:36
ReduceFilterOp(const ReduceFilterOp &other, tbb::split)
Definition: NodeManager.h:766
Index64 nodeCount() const
Definition: NodeManager.h:63
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:54
RootNodeType & mRoot
Definition: NodeManager.h:1038
std::unique_ptr< NodeT *[]> mNodePtrs
Definition: NodeManager.h:389
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:232
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:892
Definition: NodeManager.h:44
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:538
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
bool empty() const
Definition: NodeManager.h:204
Definition: Coord.h:587
Definition: NodeManager.h:724
OpT & op()
Definition: NodeManager.h:787
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
bool initNodeChildren(ParentsT &parents, const NodeFilterT &nodeFilter=NodeFilterT(), bool serial=false)
Definition: NodeManager.h:105
const NodeList & nodeList() const
Definition: NodeManager.h:202
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:889
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:191
const NodeRange & nodeRange() const
Definition: NodeManager.h:237
size_t grainsize() const
Definition: NodeManager.h:200
bool is_divisible() const
Definition: NodeManager.h:206
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
Index32 Index
Definition: openvdb/Types.h:50
Iterator begin() const
Definition: NodeManager.h:244
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:211
const NonConstRootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:900
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:558
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:224
static bool valid(size_t)
Definition: NodeManager.h:46
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:231
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:194
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:736
Definition: openvdb/Exceptions.h:13
ReduceFilterOp(const ReduceFilterOp &other)
Definition: NodeManager.h:762
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:218
uint64_t Index64
Definition: openvdb/Types.h:49
typename std::remove_const< ToType >::type Type
Definition: openvdb/Types.h:317
bool valid(size_t idx) const
Definition: NodeManager.h:741
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:220
RootNodeType & mRoot
Definition: NodeManager.h:713
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:891
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 run(const char *ax, openvdb::GridBase &grid)
Run a full AX pipeline (parse, compile and execute) on a single OpenVDB Grid.
bool operator==(const Iterator &other) const
Definition: NodeManager.h:236
NodeT & operator()(size_t n) const
Definition: NodeManager.h:59
DynamicNodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:1039
Definition: Coord.h:16
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:227
void reduceWithIndex(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:292
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:275
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
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:772
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:611
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:536
bool initRootChildren(RootT &root)
Definition: NodeManager.h:74
void clear()
Definition: NodeManager.h:65
NodeT *& operator[](size_t n)
Definition: NodeManager.h:61
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
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:890
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:539
DynamicNodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:895
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:537
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:561
NodeManager(TreeOrLeafManagerT &tree, bool serial=false)
Definition: NodeManager.h:542
Definition: NodeManager.h:755
ForeachFilterOp(const ForeachFilterOp &other)
Definition: NodeManager.h:731
bool valid(size_t idx) const
Definition: NodeManager.h:782
size_t size() const
Definition: NodeManager.h:198
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:178
Definition: NodeManager.h:187
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:222
void foreachWithIndex(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:284