HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
TreeIterator.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: Apache-2.0
3 //
4 /// @file tree/TreeIterator.h
5 
6 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
7 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
8 
9 #include <tbb/blocked_range.h>
10 #include <tbb/parallel_for.h>
11 #include <openvdb/version.h>
12 #include <openvdb/Types.h>
13 #include <openvdb/util/Assert.h>
14 #include <algorithm>
15 #include <sstream>
16 #include <string>
17 #include <type_traits>
18 
19 // Prior to 0.96.1, depth-bounded value iterators always descended to the leaf level
20 // and iterated past leaf nodes. Now, they never descend past the maximum depth.
21 // Comment out the following line to restore the older, less-efficient behavior:
22 #define ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
23 
24 
25 namespace openvdb {
27 namespace OPENVDB_VERSION_NAME {
28 namespace tree {
29 
30 namespace iter {
31 
32 template<typename HeadT, int HeadLevel>
33 struct InvertedTree {
34  using SubtreeT = typename InvertedTree<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
35  using Type = typename SubtreeT::template Append<HeadT>;
36 };
37 template<typename HeadT>
38 struct InvertedTree<HeadT, /*HeadLevel=*/1> {
40 };
41 
42 } // namespace iter
43 
44 
45 ////////////////////////////////////////
46 
47 
48 /// IterTraits provides the following for iterators of the standard types,
49 /// i.e., for {Child,Value}{On,Off,All}{Iter,CIter}:
50 /// - a NodeConverter template to convert an iterator for one type of node
51 /// to an iterator of the same type for another type of node; for example,
52 /// IterTraits<RootNode, RootNode::ValueOnIter>::NodeConverter<LeafNode>::Type
53 /// is synonymous with LeafNode::ValueOnIter.
54 /// - a begin(node) function that returns a begin iterator for a node of arbitrary type;
55 /// for example, IterTraits<LeafNode, LeafNode::ValueOnIter>::begin(leaf) returns
56 /// leaf.beginValueOn()
57 /// - a getChild() function that returns a pointer to the child node to which the iterator
58 /// is currently pointing (always null if the iterator is a Value iterator)
59 template<typename NodeT, typename IterT>
60 struct IterTraits
61 {
62  template<typename ChildT> static ChildT* getChild(const IterT&) { return nullptr; }
63 };
64 
65 template<typename NodeT>
66 struct IterTraits<NodeT, typename NodeT::ChildOnIter>
67 {
68  using IterT = typename NodeT::ChildOnIter;
69  static IterT begin(NodeT& node) { return node.beginChildOn(); }
70  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
71  return &iter.getValue();
72  }
73  template<typename OtherNodeT> struct NodeConverter {
74  using Type = typename OtherNodeT::ChildOnIter;
75  };
76 };
77 
78 template<typename NodeT>
79 struct IterTraits<NodeT, typename NodeT::ChildOnCIter>
80 {
81  using IterT = typename NodeT::ChildOnCIter;
82  static IterT begin(const NodeT& node) { return node.cbeginChildOn(); }
83  template<typename ChildT> static const ChildT* getChild(const IterT& iter) {
84  return &iter.getValue();
85  }
86  template<typename OtherNodeT> struct NodeConverter {
87  using Type = typename OtherNodeT::ChildOnCIter;
88  };
89 };
90 
91 template<typename NodeT>
92 struct IterTraits<NodeT, typename NodeT::ChildOffIter>
93 {
94  using IterT = typename NodeT::ChildOffIter;
95  static IterT begin(NodeT& node) { return node.beginChildOff(); }
96  template<typename OtherNodeT> struct NodeConverter {
97  using Type = typename OtherNodeT::ChildOffIter;
98  };
99 };
100 
101 template<typename NodeT>
102 struct IterTraits<NodeT, typename NodeT::ChildOffCIter>
103 {
104  using IterT = typename NodeT::ChildOffCIter;
105  static IterT begin(const NodeT& node) { return node.cbeginChildOff(); }
106  template<typename OtherNodeT> struct NodeConverter {
107  using Type = typename OtherNodeT::ChildOffCIter;
108  };
109 };
110 
111 template<typename NodeT>
112 struct IterTraits<NodeT, typename NodeT::ChildAllIter>
113 {
114  using IterT = typename NodeT::ChildAllIter;
115  static IterT begin(NodeT& node) { return node.beginChildAll(); }
116  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
117  typename IterT::NonConstValueType val;
118  return iter.probeChild(val);
119  }
120  template<typename OtherNodeT> struct NodeConverter {
121  using Type = typename OtherNodeT::ChildAllIter;
122  };
123 };
124 
125 template<typename NodeT>
126 struct IterTraits<NodeT, typename NodeT::ChildAllCIter>
127 {
128  using IterT = typename NodeT::ChildAllCIter;
129  static IterT begin(const NodeT& node) { return node.cbeginChildAll(); }
130  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
131  typename IterT::NonConstValueType val;
132  return iter.probeChild(val);
133  }
134  template<typename OtherNodeT> struct NodeConverter {
135  using Type = typename OtherNodeT::ChildAllCIter;
136  };
137 };
138 
139 template<typename NodeT>
140 struct IterTraits<NodeT, typename NodeT::ValueOnIter>
141 {
142  using IterT = typename NodeT::ValueOnIter;
143  static IterT begin(NodeT& node) { return node.beginValueOn(); }
144  template<typename OtherNodeT> struct NodeConverter {
145  using Type = typename OtherNodeT::ValueOnIter;
146  };
147 };
148 
149 template<typename NodeT>
150 struct IterTraits<NodeT, typename NodeT::ValueOnCIter>
151 {
152  using IterT = typename NodeT::ValueOnCIter;
153  static IterT begin(const NodeT& node) { return node.cbeginValueOn(); }
154  template<typename OtherNodeT> struct NodeConverter {
155  using Type = typename OtherNodeT::ValueOnCIter;
156  };
157 };
158 
159 template<typename NodeT>
160 struct IterTraits<NodeT, typename NodeT::ValueOffIter>
161 {
162  using IterT = typename NodeT::ValueOffIter;
163  static IterT begin(NodeT& node) { return node.beginValueOff(); }
164  template<typename OtherNodeT> struct NodeConverter {
165  using Type = typename OtherNodeT::ValueOffIter;
166  };
167 };
168 
169 template<typename NodeT>
170 struct IterTraits<NodeT, typename NodeT::ValueOffCIter>
171 {
172  using IterT = typename NodeT::ValueOffCIter;
173  static IterT begin(const NodeT& node) { return node.cbeginValueOff(); }
174  template<typename OtherNodeT> struct NodeConverter {
175  using Type = typename OtherNodeT::ValueOffCIter;
176  };
177 };
178 
179 template<typename NodeT>
180 struct IterTraits<NodeT, typename NodeT::ValueAllIter>
181 {
182  using IterT = typename NodeT::ValueAllIter;
183  static IterT begin(NodeT& node) { return node.beginValueAll(); }
184  template<typename OtherNodeT> struct NodeConverter {
185  using Type = typename OtherNodeT::ValueAllIter;
186  };
187 };
188 
189 template<typename NodeT>
190 struct IterTraits<NodeT, typename NodeT::ValueAllCIter>
191 {
192  using IterT = typename NodeT::ValueAllCIter;
193  static IterT begin(const NodeT& node) { return node.cbeginValueAll(); }
194  template<typename OtherNodeT> struct NodeConverter {
195  using Type = typename OtherNodeT::ValueAllCIter;
196  };
197 };
198 
199 
200 ////////////////////////////////////////
201 
202 
203 /// @brief An IterListItem is an element of a compile-time linked list of iterators
204 /// to nodes of different types.
205 ///
206 /// The list is constructed by traversing the template hierarchy of a Tree in reverse order,
207 /// so typically the elements will be a LeafNode iterator of some type (e.g., ValueOnCIter),
208 /// followed by one or more InternalNode iterators of the same type, followed by a RootNode
209 /// iterator of the same type.
210 ///
211 /// The length of the list is fixed at compile time, and because it is implemented using
212 /// nested, templated classes, much of the list traversal logic can be optimized away.
213 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level>
215 {
216 public:
217  /// The type of iterator stored in the previous list item
218  using PrevIterT = typename PrevItemT::IterT;
219  /// The type of node (non-const) whose iterator is stored in this list item
220  using _NodeT = typename NodeVecT::Front;
221  /// The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
224 
225  /// The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
226  using NodeT = typename IterT::NodeType;
227  /// The type of the node with const qualifiers removed ("Non-Const")
228  using NCNodeT = typename IterT::NonConstNodeType;
229  /// The type of value (with const qualifiers removed) to which the iterator points
230  using NCValueT = typename IterT::NonConstValueType;
231  /// NodeT's child node type, with the same constness (e.g., const InternalNode<...>)
233  /// NodeT's child node type with const qualifiers removed
236  /// NodeT's level in its tree (0 = LeafNode)
237  static const Index Level = _Level;
238 
239  IterListItem(PrevItemT* prev): mNext(this), mPrev(prev) {}
240 
241  IterListItem(const IterListItem& other):
242  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
244  {
245  if (&other != this) {
246  mIter = other.mIter;
247  mNext = other.mNext;
248  mPrev = nullptr; ///< @note external call to updateBackPointers() required
249  }
250  return *this;
251  }
252 
253  void updateBackPointers(PrevItemT* prev) { mPrev = prev; mNext.updateBackPointers(this); }
254 
255  void setIter(const IterT& iter) { mIter = iter; }
256  template<typename OtherIterT>
257  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
258 
259  /// Return the node over which this list element's iterator iterates.
260  void getNode(Index lvl, NodeT*& node) const
261  {
262  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
263  }
264  /// Return the node over which one of the following list elements' iterator iterates.
265  template<typename OtherNodeT>
266  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
267 
268  /// @brief Initialize the iterator for level @a lvl of the tree with the node
269  /// over which the corresponding iterator of @a otherListItem is iterating.
270  ///
271  /// For example, if @a otherListItem contains a LeafNode::ValueOnIter,
272  /// initialize this list's leaf iterator with the same LeafNode.
273  template<typename OtherIterListItemT>
274  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
275  {
276  if (lvl == Level) {
277  const NodeT* node = nullptr;
278  otherListItem.getNode(lvl, node);
279  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
280  } else {
281  // Forward to one of the following list elements.
282  mNext.initLevel(lvl, otherListItem);
283  }
284  }
285 
286  /// Return The table offset of the iterator at level @a lvl of the tree.
287  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
288 
289  /// Return @c true if the iterator at level @a lvl of the tree has not yet reached its end.
290  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
291 
292  /// Increment the iterator at level @a lvl of the tree.
293  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
294 
295  /// @brief If the iterator at level @a lvl of the tree points to a child node,
296  /// initialize the next iterator in this list with that child node.
297  bool down(Index lvl)
298  {
299  if (lvl == Level && mPrev != nullptr && mIter) {
300  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
301  mPrev->setIter(PrevItemT::ITraits::begin(*child));
302  return true;
303  }
304  }
305  return (lvl > Level) ? mNext.down(lvl) : false;
306  }
307 
308  /// @brief Return the global coordinates of the voxel or tile to which the iterator
309  /// at level @a lvl of the tree is currently pointing.
310  Coord getCoord(Index lvl) const
311  {
312  return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
313  }
315  {
316  return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
317  }
318  /// Return the number of (virtual) voxels spanned by a tile value or child node
320  {
321  return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
322  }
323 
324  /// Return @c true if the iterator at level @a lvl of the tree points to an active value.
325  bool isValueOn(Index lvl) const
326  {
327  return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
328  }
329 
330  /// Return the value to which the iterator at level @a lvl of the tree points.
331  const NCValueT& getValue(Index lvl) const
332  {
333  if (lvl == Level) return mIter.getValue();
334  return mNext.getValue(lvl);
335  }
336 
337  /// @brief Set the value (to @a val) to which the iterator at level @a lvl
338  /// of the tree points and mark the value as active.
339  /// @note Not valid when @c IterT is a const iterator type
340  void setValue(Index lvl, const NCValueT& val) const
341  {
342  if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val);
343  }
344  /// @brief Set the value (to @a val) to which the iterator at level @a lvl of the tree
345  /// points and mark the value as active if @a on is @c true, or inactive otherwise.
346  /// @note Not valid when @c IterT is a const iterator type
347  void setValueOn(Index lvl, bool on = true) const
348  {
349  if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
350  }
351  /// @brief Mark the value to which the iterator at level @a lvl of the tree points
352  /// as inactive.
353  /// @note Not valid when @c IterT is a const iterator type
354  void setValueOff(Index lvl) const
355  {
356  if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl);
357  }
358 
359  /// @brief Apply a functor to the item to which this iterator is pointing.
360  /// @note Not valid when @c IterT is a const iterator type
361  template<typename ModifyOp>
362  void modifyValue(Index lvl, const ModifyOp& op) const
363  {
364  if (lvl == Level) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
365  }
366 
367 private:
368  using RestT = typename NodeVecT::PopFront; // NodeVecT minus its first item
369  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, Level + 1>;
370 
371  IterT mIter;
372  NextItem mNext;
373  PrevItemT* mPrev;
374 };
375 
376 
377 /// The initial element of a compile-time linked list of iterators to nodes of different types
378 template<typename PrevItemT, typename NodeVecT, size_t VecSize>
379 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U>
380 {
381 public:
382  /// The type of iterator stored in the previous list item
383  using PrevIterT = typename PrevItemT::IterT;
384  /// The type of node (non-const) whose iterator is stored in this list item
385  using _NodeT = typename NodeVecT::Front;
386  /// The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
389 
390  /// The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
391  using NodeT = typename IterT::NodeType;
392  /// The type of the node with const qualifiers removed ("Non-Const")
393  using NCNodeT = typename IterT::NonConstNodeType;
394  /// The type of value (with const qualifiers removed) to which the iterator points
395  using NCValueT = typename IterT::NonConstValueType;
397  /// NodeT's level in its tree (0 = LeafNode)
398  static const Index Level = 0;
399 
400  IterListItem(PrevItemT*): mNext(this), mPrev(nullptr) {}
401 
402  IterListItem(const IterListItem& other):
403  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
405  {
406  if (&other != this) {
407  mIter = other.mIter;
408  mNext = other.mNext;
409  mPrev = nullptr;
410  }
411  return *this;
412  }
413 
414  void updateBackPointers(PrevItemT* = nullptr)
415  {
416  mPrev = nullptr; mNext.updateBackPointers(this);
417  }
418 
419  void setIter(const IterT& iter) { mIter = iter; }
420  template<typename OtherIterT>
421  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
422 
423  void getNode(Index lvl, NodeT*& node) const
424  {
425  node = (lvl == 0) ? mIter.getParentNode() : nullptr;
426  }
427  template<typename OtherNodeT>
428  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
429 
430  template<typename OtherIterListItemT>
431  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
432  {
433  if (lvl == 0) {
434  const NodeT* node = nullptr;
435  otherListItem.getNode(lvl, node);
436  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
437  } else {
438  mNext.initLevel(lvl, otherListItem);
439  }
440  }
441 
442  Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
443 
444  bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
445 
446  bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
447 
448  bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); }
449 
450  Coord getCoord(Index lvl) const
451  {
452  return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
453  }
455  {
456  return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
457  }
458 
460  {
461  return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
462  }
463 
464  bool isValueOn(Index lvl) const
465  {
466  return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
467  }
468 
469  const NCValueT& getValue(Index lvl) const
470  {
471  if (lvl == 0) return mIter.getValue();
472  return mNext.getValue(lvl);
473  }
474 
475  void setValue(Index lvl, const NCValueT& val) const
476  {
477  if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val);
478  }
479  void setValueOn(Index lvl, bool on = true) const
480  {
481  if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
482  }
483  void setValueOff(Index lvl) const
484  {
485  if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl);
486  }
487 
488  template<typename ModifyOp>
489  void modifyValue(Index lvl, const ModifyOp& op) const
490  {
491  if (lvl == 0) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
492  }
493 
494 private:
495  using RestT = typename NodeVecT::PopFront; // NodeVecT minus its first item
496  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1>;
497 
498  IterT mIter;
499  NextItem mNext;
500  PrevItemT* mPrev;
501 };
502 
503 
504 /// The final element of a compile-time linked list of iterators to nodes of different types
505 template<typename PrevItemT, typename NodeVecT, Index _Level>
506 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level>
507 {
508 public:
509  using _NodeT = typename NodeVecT::Front;
510  /// The type of iterator stored in the previous list item
511  using PrevIterT = typename PrevItemT::IterT;
512  /// The type of iterator stored in this list item (e.g., RootNode::ValueOnCIter)
515 
516  /// The type of node over which IterT iterates (e.g., const RootNode<...>)
517  using NodeT = typename IterT::NodeType;
518  /// The type of the node with const qualifiers removed ("Non-Const")
519  using NCNodeT = typename IterT::NonConstNodeType;
520  /// The type of value (with const qualifiers removed) to which the iterator points
521  using NCValueT = typename IterT::NonConstValueType;
522  /// NodeT's child node type, with the same constness (e.g., const InternalNode<...>)
524  /// NodeT's child node type with const qualifiers removed
527  /// NodeT's level in its tree (0 = LeafNode)
528  static const Index Level = _Level;
529 
530  IterListItem(PrevItemT* prev): mPrev(prev) {}
531 
532  IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(nullptr) {}
534  {
535  if (&other != this) {
536  mIter = other.mIter;
537  mPrev = nullptr; ///< @note external call to updateBackPointers() required
538  }
539  return *this;
540  }
541 
542  void updateBackPointers(PrevItemT* prev) { mPrev = prev; }
543 
544  // The following method specializations differ from the default template
545  // implementations mainly in that they don't forward.
546 
547  void setIter(const IterT& iter) { mIter = iter; }
548 
549  void getNode(Index lvl, NodeT*& node) const
550  {
551  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
552  }
553 
554  template<typename OtherIterListItemT>
555  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
556  {
557  if (lvl == Level) {
558  const NodeT* node = nullptr;
559  otherListItem.getNode(lvl, node);
560  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
561  }
562  }
563 
564  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); }
565 
566  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; }
567 
568  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; }
569 
570  bool down(Index lvl)
571  {
572  if (lvl == Level && mPrev != nullptr && mIter) {
573  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
574  mPrev->setIter(PrevItemT::ITraits::begin(*child));
575  return true;
576  }
577  }
578  return false;
579  }
580 
581  Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); }
582  Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; }
583  Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; }
584 
585  bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; }
586 
587  const NCValueT& getValue(Index lvl) const
588  {
589  OPENVDB_ASSERT(lvl == Level);
590  (void)lvl; // avoid unused variable warning in optimized builds
591  return mIter.getValue();
592  }
593 
594  void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); }
595  void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); }
596  void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); }
597 
598  template<typename ModifyOp>
599  void modifyValue(Index lvl, const ModifyOp& op) const
600  {
601  if (lvl == Level) mIter.modifyValue(op);
602  }
603 
604 private:
605  IterT mIter;
606  PrevItemT* mPrev;
607 };
608 
609 
610 ////////////////////////////////////////
611 
612 
613 //#define DEBUG_TREE_VALUE_ITERATOR
614 
615 /// @brief Base class for tree-traversal iterators over tile and voxel values
616 template<typename _TreeT, typename _ValueIterT>
618 {
619 public:
620  using TreeT = _TreeT;
621  using ValueIterT = _ValueIterT;
622  using NodeT = typename ValueIterT::NodeType;
623  using ValueT = typename ValueIterT::NonConstValueType;
624  using ChildOnIterT = typename NodeT::ChildOnCIter;
625  static const Index ROOT_LEVEL = NodeT::LEVEL;
626  static_assert(ValueIterT::NodeType::LEVEL == ROOT_LEVEL, "invalid value iterator node type");
627  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
628 
630 
633 
634  /// Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
635  void setMinDepth(Index minDepth);
636  /// Return the depth of the highest level of the tree to which this iterator ascends.
637  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
638  /// Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
639  void setMaxDepth(Index maxDepth);
640  /// Return the depth of the lowest level of the tree to which this iterator ascends.
641  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
642 
643  //@{
644  /// Return @c true if this iterator is not yet exhausted.
645  bool test() const { return mValueIterList.test(mLevel); }
646  operator bool() const { return this->test(); }
647  //@}
648 
649  /// @brief Advance to the next tile or voxel value.
650  /// Return @c true if this iterator is not yet exhausted.
651  bool next();
652  /// Advance to the next tile or voxel value.
653  TreeValueIteratorBase& operator++() { this->next(); return *this; }
654 
655  /// @brief Return the level in the tree (0 = leaf) of the node to which
656  /// this iterator is currently pointing.
657  Index getLevel() const { return mLevel; }
658  /// @brief Return the depth in the tree (0 = root) of the node to which
659  /// this iterator is currently pointing.
660  Index getDepth() const { return ROOT_LEVEL - mLevel; }
661  static Index getLeafDepth() { return LEAF_DEPTH; }
662 
663  /// @brief Return in @a node a pointer to the node over which this iterator is
664  /// currently iterating or one of that node's parents, as determined by @a NodeType.
665  /// Sets @a node to null pointer if @a NodeType specifies a node at a lower level
666  /// of the tree than that given by getLevel().
667  template<typename NodeType>
668  void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); }
669 
670  /// @brief Return the global coordinates of the voxel or tile to which
671  /// this iterator is currently pointing.
672  Coord getCoord() const { return mValueIterList.getCoord(mLevel); }
673  /// @brief Return in @a bbox the axis-aligned bounding box of
674  /// the voxel or tile to which this iterator is currently pointing.
675  /// @return false if the bounding box is empty.
676  bool getBoundingBox(CoordBBox&) const;
677  /// @brief Return the axis-aligned bounding box of the voxel or tile to which
678  /// this iterator is currently pointing.
679  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
680 
681  /// Return the number of (virtual) voxels corresponding to the value
682  Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);}
683 
684  /// Return @c true if this iterator is currently pointing to a (non-leaf) tile value.
685  bool isTileValue() const { return mLevel != 0 && this->test(); }
686  /// Return @c true if this iterator is currently pointing to a (leaf) voxel value.
687  bool isVoxelValue() const { return mLevel == 0 && this->test(); }
688  /// Return @c true if the value to which this iterator is currently pointing is active.
689  bool isValueOn() const { return mValueIterList.isValueOn(mLevel); }
690 
691  //@{
692  /// Return the tile or voxel value to which this iterator is currently pointing.
693  const ValueT& getValue() const { return mValueIterList.getValue(mLevel); }
694  const ValueT& operator*() const { return this->getValue(); }
695  const ValueT* operator->() const { return &(this->operator*()); }
696  //@}
697 
698  /// @brief Change the tile or voxel value to which this iterator is currently pointing
699  /// and mark it as active.
700  void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); }
701  /// @brief Change the active/inactive state of the tile or voxel value to which
702  /// this iterator is currently pointing.
703  void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); }
704  /// Mark the tile or voxel value to which this iterator is currently pointing as inactive.
705  void setValueOff() const { mValueIterList.setValueOff(mLevel); }
706 
707  /// @brief Apply a functor to the item to which this iterator is pointing.
708  /// (Not valid for const iterators.)
709  /// @param op a functor of the form <tt>void op(ValueType&) const</tt> that modifies
710  /// its argument in place
711  /// @see Tree::modifyValue()
712  template<typename ModifyOp>
713  void modifyValue(const ModifyOp& op) const { mValueIterList.modifyValue(mLevel, op); }
714 
715  /// Return a pointer to the tree over which this iterator is iterating.
716  TreeT* getTree() const { return mTree; }
717 
718  /// Return a string (for debugging, mainly) describing this iterator's current state.
719  std::string summary() const;
720 
721 private:
722  bool advance(bool dontIncrement = false);
723 
724  using InvTreeT = typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type;
725  struct PrevChildItem { using IterT = ChildOnIterT; };
726  struct PrevValueItem { using IterT = ValueIterT; };
727 
728  IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList;
729  IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList;
730  Index mLevel;
731  int mMinLevel, mMaxLevel;
732  TreeT* mTree;
733 }; // class TreeValueIteratorBase
734 
735 
736 template<typename TreeT, typename ValueIterT>
737 inline
739  mChildIterList(nullptr),
740  mValueIterList(nullptr),
741  mLevel(ROOT_LEVEL),
742  mMinLevel(int(LEAF_LEVEL)),
743  mMaxLevel(int(ROOT_LEVEL)),
744  mTree(&tree)
745 {
746  mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.root()));
747  mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.root()));
748  this->advance(/*dontIncrement=*/true);
749 }
750 
751 
752 template<typename TreeT, typename ValueIterT>
753 inline
755  mChildIterList(other.mChildIterList),
756  mValueIterList(other.mValueIterList),
757  mLevel(other.mLevel),
758  mMinLevel(other.mMinLevel),
759  mMaxLevel(other.mMaxLevel),
760  mTree(other.mTree)
761 {
762  mChildIterList.updateBackPointers();
763  mValueIterList.updateBackPointers();
764 }
765 
766 
767 template<typename TreeT, typename ValueIterT>
770 {
771  if (&other != this) {
772  mChildIterList = other.mChildIterList;
773  mValueIterList = other.mValueIterList;
774  mLevel = other.mLevel;
775  mMinLevel = other.mMinLevel;
776  mMaxLevel = other.mMaxLevel;
777  mTree = other.mTree;
778  mChildIterList.updateBackPointers();
779  mValueIterList.updateBackPointers();
780  }
781  return *this;
782 }
783 
784 
785 template<typename TreeT, typename ValueIterT>
786 inline void
788 {
789  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
790  if (int(mLevel) > mMaxLevel) this->next();
791 }
792 
793 
794 template<typename TreeT, typename ValueIterT>
795 inline void
797 {
798  // level = ROOT_LEVEL - depth
799  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
800  if (int(mLevel) < mMinLevel) this->next();
801 }
802 
803 
804 template<typename TreeT, typename ValueIterT>
805 inline bool
807 {
808  do {
809  if (!this->advance()) return false;
810  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
811  return true;
812 }
813 
814 
815 template<typename TreeT, typename ValueIterT>
816 inline bool
818 {
819  bool recurse = false;
820  do {
821  recurse = false;
822  Index
823  vPos = mValueIterList.pos(mLevel),
824  cPos = mChildIterList.pos(mLevel);
825  if (vPos == cPos && mChildIterList.test(mLevel)) {
826  /// @todo Once ValueOff iterators properly skip child pointers, remove this block.
827  mValueIterList.next(mLevel);
828  vPos = mValueIterList.pos(mLevel);
829  }
830  if (vPos < cPos) {
831  if (dontIncrement) return true;
832  if (mValueIterList.next(mLevel)) {
833  if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
834  /// @todo Once ValueOff iterators properly skip child pointers,
835  /// remove this block.
836  mValueIterList.next(mLevel);
837  }
838  // If there is a next value and it precedes the next child, return.
839  if (mValueIterList.pos(mLevel) < cPos) return true;
840  }
841  } else {
842  // Advance to the next child, which may or may not precede the next value.
843  if (!dontIncrement) mChildIterList.next(mLevel);
844  }
845 #ifdef DEBUG_TREE_VALUE_ITERATOR
846  std::cout << "\n" << this->summary() << std::flush;
847 #endif
848 
849  // Descend to the lowest level at which the next value precedes the next child.
850  while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
851 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
852  if (int(mLevel) == mMinLevel) {
853  // If the current node lies at the lowest allowed level, none of its
854  // children can be visited, so just advance its child iterator.
855  mChildIterList.next(mLevel);
856  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
857  && mChildIterList.test(mLevel))
858  {
859  /// @todo Once ValueOff iterators properly skip child pointers,
860  /// remove this block.
861  mValueIterList.next(mLevel);
862  }
863  } else
864 #endif
865  if (mChildIterList.down(mLevel)) {
866  --mLevel; // descend one level
867  mValueIterList.initLevel(mLevel, mChildIterList);
868  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
869  && mChildIterList.test(mLevel))
870  {
871  /// @todo Once ValueOff iterators properly skip child pointers,
872  /// remove this block.
873  mValueIterList.next(mLevel);
874  }
875  } else break;
876 #ifdef DEBUG_TREE_VALUE_ITERATOR
877  std::cout << "\n" << this->summary() << std::flush;
878 #endif
879  }
880  // Ascend to the nearest level at which one of the iterators is not yet exhausted.
881  while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
882  if (mLevel == ROOT_LEVEL) return false;
883  ++mLevel;
884  mChildIterList.next(mLevel);
885  dontIncrement = true;
886  recurse = true;
887  }
888  } while (recurse);
889  return true;
890 }
891 
892 
893 template<typename TreeT, typename ValueIterT>
894 inline bool
896 {
897  if (!this->test()) {
898  bbox = CoordBBox();
899  return false;
900  }
901  bbox.min() = mValueIterList.getCoord(mLevel);
902  bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1);
903  return true;
904 }
905 
906 
907 template<typename TreeT, typename ValueIterT>
908 inline std::string
910 {
911  std::ostringstream ostr;
912  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
913  if (lvl == 0) ostr << "leaf";
914  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
915  else ostr << "int" << (ROOT_LEVEL - lvl);
916  ostr << " v" << mValueIterList.pos(lvl)
917  << " c" << mChildIterList.pos(lvl);
918  if (lvl > int(mLevel)) ostr << " / ";
919  }
920  if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
921  if (mLevel == 0) {
922  ostr << " " << this->getCoord();
923  } else {
924  ostr << " " << this->getBoundingBox();
925  }
926  }
927  return ostr.str();
928 }
929 
930 
931 ////////////////////////////////////////
932 
933 
934 /// @brief Base class for tree-traversal iterators over all nodes
935 template<typename _TreeT, typename RootChildOnIterT>
937 {
938 public:
939  using TreeT = _TreeT;
940  using RootIterT = RootChildOnIterT;
941  using RootNodeT = typename RootIterT::NodeType;
942  using NCRootNodeT = typename RootIterT::NonConstNodeType;
943  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
945  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
946 
948 
951 
952  NodeIteratorBase(const NodeIteratorBase& other);
954 
955  /// Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
956  void setMinDepth(Index minDepth);
957  /// Return the depth of the highest level of the tree to which this iterator ascends.
958  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
959  /// Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
960  void setMaxDepth(Index maxDepth);
961  /// Return the depth of the lowest level of the tree to which this iterator ascends.
962  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
963 
964  //@{
965  /// Return @c true if this iterator is not yet exhausted.
966  bool test() const { return !mDone; }
967  operator bool() const { return this->test(); }
968  //@}
969 
970  /// @brief Advance to the next tile or voxel value.
971  /// @return @c true if this iterator is not yet exhausted.
972  bool next();
973  /// Advance the iterator to the next leaf node.
974  void increment() { this->next(); }
975  NodeIteratorBase& operator++() { this->increment(); return *this; }
976  /// Increment the iterator n times.
977  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
978 
979  /// @brief Return the level in the tree (0 = leaf) of the node to which
980  /// this iterator is currently pointing.
981  Index getLevel() const { return mLevel; }
982  /// @brief Return the depth in the tree (0 = root) of the node to which
983  /// this iterator is currently pointing.
984  Index getDepth() const { return ROOT_LEVEL - mLevel; }
985  static Index getLeafDepth() { return LEAF_DEPTH; }
986 
987  /// @brief Return the global coordinates of the voxel or tile to which
988  /// this iterator is currently pointing.
989  Coord getCoord() const;
990  /// @brief Return in @a bbox the axis-aligned bounding box of
991  /// the voxel or tile to which this iterator is currently pointing.
992  /// @return false if the bounding box is empty.
993  bool getBoundingBox(CoordBBox& bbox) const;
994  /// @brief Return the axis-aligned bounding box of the voxel or tile to which
995  /// this iterator is currently pointing.
996  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
997 
998  //@{
999  /// @brief Return the node to which the iterator is pointing.
1000  /// @note This iterator doesn't have the usual dereference operators (* and ->),
1001  /// because they would have to be overloaded by the returned node type.
1002  template<typename NodeT>
1003  void getNode(NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1004  template<typename NodeT>
1005  void getNode(const NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1006  //@}
1007 
1008  TreeT* getTree() const { return mTree; }
1009 
1010  std::string summary() const;
1011 
1012 private:
1013  struct PrevItem { using IterT = RootIterT; };
1014 
1015  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1016  Index mLevel;
1017  int mMinLevel, mMaxLevel;
1018  bool mDone;
1019  TreeT* mTree;
1020 }; // class NodeIteratorBase
1021 
1022 
1023 template<typename TreeT, typename RootChildOnIterT>
1024 inline
1026  mIterList(nullptr),
1027  mLevel(ROOT_LEVEL),
1028  mMinLevel(int(LEAF_LEVEL)),
1029  mMaxLevel(int(ROOT_LEVEL)),
1030  mDone(true),
1031  mTree(nullptr)
1032 {
1033 }
1034 
1035 
1036 template<typename TreeT, typename RootChildOnIterT>
1037 inline
1039  mIterList(nullptr),
1040  mLevel(ROOT_LEVEL),
1041  mMinLevel(int(LEAF_LEVEL)),
1042  mMaxLevel(int(ROOT_LEVEL)),
1043  mDone(false),
1044  mTree(&tree)
1045 {
1046  mIterList.setIter(RootIterTraits::begin(tree.root()));
1047 }
1048 
1049 
1050 template<typename TreeT, typename RootChildOnIterT>
1051 inline
1053  mIterList(other.mIterList),
1054  mLevel(other.mLevel),
1055  mMinLevel(other.mMinLevel),
1056  mMaxLevel(other.mMaxLevel),
1057  mDone(other.mDone),
1058  mTree(other.mTree)
1059 {
1060  mIterList.updateBackPointers();
1061 }
1062 
1063 
1064 template<typename TreeT, typename RootChildOnIterT>
1067 {
1068  if (&other != this) {
1069  mLevel = other.mLevel;
1070  mMinLevel = other.mMinLevel;
1071  mMaxLevel = other.mMaxLevel;
1072  mDone = other.mDone;
1073  mTree = other.mTree;
1074  mIterList = other.mIterList;
1075  mIterList.updateBackPointers();
1076  }
1077  return *this;
1078 }
1079 
1080 
1081 template<typename TreeT, typename RootChildOnIterT>
1082 inline void
1084 {
1085  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
1086  if (int(mLevel) > mMaxLevel) this->next();
1087 }
1088 
1089 
1090 template<typename TreeT, typename RootChildOnIterT>
1091 inline void
1093 {
1094  // level = ROOT_LEVEL - depth
1095  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
1096  if (int(mLevel) < mMinLevel) this->next();
1097 }
1098 
1099 
1100 template<typename TreeT, typename RootChildOnIterT>
1101 inline bool
1103 {
1104  do {
1105  if (mDone) return false;
1106 
1107  // If the iterator over the current node points to a child,
1108  // descend to the child (depth-first traversal).
1109  if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1110  if (!mIterList.down(mLevel)) return false;
1111  --mLevel;
1112  } else {
1113  // Ascend to the nearest ancestor that has other children.
1114  while (!mIterList.test(mLevel)) {
1115  if (mLevel == ROOT_LEVEL) {
1116  // Can't ascend higher than the root.
1117  mDone = true;
1118  return false;
1119  }
1120  ++mLevel; // ascend one level
1121  mIterList.next(mLevel); // advance to the next child, if there is one
1122  }
1123  // Descend to the child.
1124  if (!mIterList.down(mLevel)) return false;
1125  --mLevel;
1126  }
1127  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1128  return true;
1129 }
1130 
1131 
1132 template<typename TreeT, typename RootChildOnIterT>
1133 inline Coord
1135 {
1136  if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1);
1137  RootNodeT* root = nullptr;
1138  this->getNode(root);
1139  return root ? root->getMinIndex() : Coord::min();
1140 }
1141 
1142 
1143 template<typename TreeT, typename RootChildOnIterT>
1144 inline bool
1146 {
1147  if (mLevel == ROOT_LEVEL) {
1148  RootNodeT* root = nullptr;
1149  this->getNode(root);
1150  if (root == nullptr) {
1151  bbox = CoordBBox();
1152  return false;
1153  }
1154  root->getIndexRange(bbox);
1155  return true;
1156  }
1157  bbox.min() = mIterList.getCoord(mLevel + 1);
1158  bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1159  return true;
1160 }
1161 
1162 
1163 template<typename TreeT, typename RootChildOnIterT>
1164 inline std::string
1166 {
1167  std::ostringstream ostr;
1168  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1169  if (lvl == 0) ostr << "leaf";
1170  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
1171  else ostr << "int" << (ROOT_LEVEL - lvl);
1172  ostr << " c" << mIterList.pos(lvl);
1173  if (lvl > int(mLevel)) ostr << " / ";
1174  }
1175  CoordBBox bbox;
1176  this->getBoundingBox(bbox);
1177  ostr << " " << bbox;
1178  return ostr.str();
1179 }
1180 
1181 
1182 ////////////////////////////////////////
1183 
1184 
1185 /// @brief Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels)
1186 template<typename TreeT, typename RootChildOnIterT>
1188 {
1189 public:
1190  using RootIterT = RootChildOnIterT;
1191  using RootNodeT = typename RootIterT::NodeType;
1192  using NCRootNodeT = typename RootIterT::NonConstNodeType;
1193  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
1195  using NCLeafNodeT = typename InvTreeT::Front;
1198 
1200 
1201  LeafIteratorBase(): mIterList(nullptr), mTree(nullptr) {}
1202 
1203  LeafIteratorBase(TreeT& tree): mIterList(nullptr), mTree(&tree)
1204  {
1205  // Initialize the iterator list with a root node iterator.
1206  mIterList.setIter(RootIterTraits::begin(tree.root()));
1207  // Descend along the first branch, initializing the node iterator at each level.
1208  Index lvl = ROOT_LEVEL;
1209  for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {}
1210  // If the first branch terminated above the leaf level, backtrack to the next branch.
1211  if (lvl > 0) this->next();
1212  }
1213 
1214  LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree)
1215  {
1216  mIterList.updateBackPointers();
1217  }
1219  {
1220  if (&other != this) {
1221  mTree = other.mTree;
1222  mIterList = other.mIterList;
1223  mIterList.updateBackPointers();
1224  }
1225  return *this;
1226  }
1227 
1228  //@{
1229  /// Return the leaf node to which the iterator is pointing.
1231  {
1232  LeafNodeT* n = nullptr;
1233  mIterList.getNode(LEAF_LEVEL, n);
1234  return n;
1235  }
1236  LeafNodeT& operator*() const { return *this->getLeaf(); }
1237  LeafNodeT* operator->() const { return this->getLeaf(); }
1238  //@}
1239 
1240  bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); }
1241  operator bool() const { return this->test(); }
1242 
1243  //@{
1244  /// Advance the iterator to the next leaf node.
1245  bool next();
1246  void increment() { this->next(); }
1247  LeafIteratorBase& operator++() { this->increment(); return *this; }
1248  //@}
1249  /// Increment the iterator n times.
1250  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1251 
1252  TreeT* getTree() const { return mTree; }
1253 
1254 private:
1255  struct PrevItem { using IterT = RootIterT; };
1256 
1257  /// @note Even though a LeafIterator doesn't iterate over leaf voxels,
1258  /// the first item of this linked list of node iterators is a leaf node iterator,
1259  /// whose purpose is only to provide access to its parent leaf node.
1260  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1261  TreeT* mTree;
1262 }; // class LeafIteratorBase
1263 
1264 
1265 template<typename TreeT, typename RootChildOnIterT>
1266 inline bool
1268 {
1269  // If the iterator is valid for the current node one level above the leaf level,
1270  // advance the iterator to the node's next child.
1271  if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1272  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1273  return true;
1274  }
1275 
1276  Index lvl = LEAF_PARENT_LEVEL;
1277  while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1278  if (mIterList.test(lvl)) {
1279  mIterList.next(lvl);
1280  } else {
1281  do {
1282  // Ascend to the nearest level at which
1283  // one of the iterators is not yet exhausted.
1284  if (lvl == ROOT_LEVEL) return false;
1285  ++lvl;
1286  if (mIterList.test(lvl)) mIterList.next(lvl);
1287  } while (!mIterList.test(lvl));
1288  }
1289  // Descend to the lowest child, but not as far as the leaf iterator.
1290  while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1291  }
1292  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1293  return true;
1294 }
1295 
1296 
1297 ////////////////////////////////////////
1298 
1299 
1300 /// An IteratorRange wraps a tree or node iterator, giving the iterator TBB
1301 /// splittable range semantics.
1302 template<typename IterT>
1304 {
1305 public:
1306  /// @brief Constructor from iterator and grain size
1307  /// @param iter Iterator from which the range is constructed
1308  /// @param grainSize Grain size which controls the granularity of range splitting
1309  IteratorRange(const IterT& iter, size_t grainSize = 8):
1310  mIter(iter),
1311  mGrainSize(grainSize),
1312  mSize(0)
1313  {
1314  mSize = this->size();
1315  }
1316 
1317  /// @brief Split constructor used by tbb (should rarely be called directly)
1318  /// @param other IteratorRange to be split
1319  /// @param tbb::split Dummy class used to create a unique signature for this constructor
1321  mIter(other.mIter),
1322  mGrainSize(other.mGrainSize),
1323  mSize(other.mSize >> 1)
1324  {
1325  other.increment(mSize);
1326  }
1327 
1328  /// @brief Return a reference to this range's iterator.
1329  /// @note The reference is const, because the iterator should not be
1330  /// incremented directly. Use this range object's increment() instead.
1331  const IterT& iterator() const { return mIter; }
1332 
1333  bool empty() const { return mSize == 0 || !mIter.test(); }
1334  bool test() const { return !this->empty(); }
1335  operator bool() const { return !this->empty(); }
1336 
1337  /// @brief Return @c true if this range is splittable (i.e., if the iterator
1338  /// can be advanced more than mGrainSize times).
1339  bool is_divisible() const { return mSize > mGrainSize; }
1340 
1341  /// Advance the iterator @a n times.
1342  void increment(size_t n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1343  /// Advance the iterator to the next item.
1344  IteratorRange& operator++() { this->increment(); return *this; }
1345  /// @brief Advance the iterator to the next item.
1346  /// @return @c true if the iterator is not yet exhausted.
1347  bool next() { this->increment(); return this->test(); }
1348 
1349 private:
1350  size_t size() const { size_t n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; }
1351 
1352  IterT mIter;
1353  size_t mGrainSize, mSize;
1354  /// @note mSize is only an estimate of the number of times mIter can be incremented
1355  /// before it is exhausted (because the topology of the underlying tree could change
1356  /// during iteration). For the purpose of range splitting, though, that should be
1357  /// sufficient, since the two halves need not be of exactly equal size.
1358 };// class IteratorRange
1359 
1360 
1361 ////////////////////////////////////////
1362 
1363 
1364 /// @brief Base class for tree-traversal iterators over real and virtual voxel values
1365 /// @todo class TreeVoxelIteratorBase;
1366 
1367 } // namespace tree
1368 } // namespace OPENVDB_VERSION_NAME
1369 } // namespace openvdb
1370 
1371 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:641
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:672
std::string summary() const
Return a string (for debugging, mainly) describing this iterator's current state. ...
Definition: TreeIterator.h:909
const NCValueT & getValue(Index lvl) const
Return the value to which the iterator at level lvl of the tree points.
Definition: TreeIterator.h:331
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:958
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:984
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
const IterT & iterator() const
Return a reference to this range's iterator.
bool down(Index lvl)
If the iterator at level lvl of the tree points to a child node, initialize the next iterator in this...
Definition: TreeIterator.h:297
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:944
bool is_divisible() const
Return true if this range is splittable (i.e., if the iterator can be advanced more than mGrainSize t...
void
Definition: png.h:1083
bool next()
Advance to the next tile or voxel value. Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:806
void getNode(const NodeT *&node) const
Return the node to which the iterator is pointing.
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:981
LeafNodeT & operator*() const
Return the leaf node to which the iterator is pointing.
typename SubtreeT::template Append< HeadT > Type
Definition: TreeIterator.h:35
void setValueOff() const
Mark the tile or voxel value to which this iterator is currently pointing as inactive.
Definition: TreeIterator.h:705
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:637
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT's child node type with const qualifiers removed.
Definition: TreeIterator.h:234
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:936
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:245
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
**But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:626
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT's child node type with const qualifiers removed.
Definition: TreeIterator.h:525
bool isValueOn(Index lvl) const
Return true if the iterator at level lvl of the tree points to an active value.
Definition: TreeIterator.h:325
void increment()
Advance the iterator to the next leaf node.
void getNode(Index lvl, NodeT *&node) const
Return the node over which this list element's iterator iterates.
Definition: TreeIterator.h:260
Coord getCoord(Index lvl) const
Return the global coordinates of the voxel or tile to which the iterator at level lvl of the tree is ...
Definition: TreeIterator.h:310
bool isValueOn() const
Return true if the value to which this iterator is currently pointing is active.
Definition: TreeIterator.h:689
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:393
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:519
void setActiveState(bool on) const
Change the active/inactive state of the tile or voxel value to which this iterator is currently point...
Definition: TreeIterator.h:703
bool test(Index lvl) const
Return true if the iterator at level lvl of the tree has not yet reached its end. ...
Definition: TreeIterator.h:290
OutGridT const XformOp bool bool
TreeValueIteratorBase & operator++()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:653
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:395
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:226
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
#define OPENVDB_ASSERT(X)
Definition: Assert.h:41
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:228
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Initialize the iterator for level lvl of the tree with the node over which the corresponding iterator...
Definition: TreeIterator.h:274
const ValueT & operator*() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:694
void increment(Index n)
Increment the iterator n times.
Definition: TreeIterator.h:977
NodeIteratorBase & operator=(const NodeIteratorBase &other)
GLdouble n
Definition: glcorearb.h:2008
Index64 getVoxelCount(Index lvl) const
Return the number of (virtual) voxels spanned by a tile value or child node.
Definition: TreeIterator.h:319
bool next()
Advance the iterator to the next item.
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:942
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:996
const ValueT & getValue() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:693
BBox< Coord > CoordBBox
Definition: NanoVDB.h:2516
TreeValueIteratorBase & operator=(const TreeValueIteratorBase &other)
Definition: TreeIterator.h:769
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:966
typename std::remove_const< ToType >::type Type
Definition: Types.h:439
const ValueT * operator->() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:695
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:645
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
Definition: TreeIterator.h:223
typename IterT::NodeType NodeT
The type of node over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:517
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:391
#define ROOT_LEVEL
Definition: CNanoVDB.h:53
typename CopyConstness< NodeT, typename NodeT::ChildNodeType >::Type ChildT
NodeT's child node type, with the same constness (e.g., const InternalNode<...>)
Definition: TreeIterator.h:523
void getNode(NodeType *&node) const
Return in node a pointer to the node over which this iterator is currently iterating or one of that n...
Definition: TreeIterator.h:668
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
typename InvertedTree< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: TreeIterator.h:34
void setValue(Index lvl, const NCValueT &val) const
Set the value (to val) to which the iterator at level lvl of the tree points and mark the value as ac...
Definition: TreeIterator.h:340
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
void setValueOn(Index lvl, bool on=true) const
Set the value (to val) to which the iterator at level lvl of the tree points and mark the value as ac...
Definition: TreeIterator.h:347
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:511
typename ValueIterT::NonConstValueType ValueT
Definition: TreeIterator.h:623
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:243
typename NodeVecT::Front _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:385
void getNode(NodeT *&node) const
Return the node to which the iterator is pointing.
Index64 getVoxelCount() const
Return the number of (virtual) voxels corresponding to the value.
Definition: TreeIterator.h:682
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., RootNode::ValueOnCIter)
Definition: TreeIterator.h:514
LeafNodeT * operator->() const
Return the leaf node to which the iterator is pointing.
bool isVoxelValue() const
Return true if this iterator is currently pointing to a (leaf) voxel value.
Definition: TreeIterator.h:687
void getNode(Index lvl, OtherNodeT *&node) const
Return the node over which one of the following list elements' iterator iterates. ...
Definition: TreeIterator.h:266
LeafIteratorBase & operator++()
Advance the iterator to the next leaf node.
GLsizeiptr size
Definition: glcorearb.h:664
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:383
LeafIteratorBase & operator=(const LeafIteratorBase &other)
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:230
Library and file format version numbers.
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
Definition: TreeIterator.h:388
Index pos(Index lvl) const
Return The table offset of the iterator at level lvl of the tree.
Definition: TreeIterator.h:287
bool next(Index lvl)
Increment the iterator at level lvl of the tree.
Definition: TreeIterator.h:293
IteratorRange(const IterT &iter, size_t grainSize=8)
Constructor from iterator and grain size.
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:974
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:796
bool next()
Advance to the next tile or voxel value.
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:617
bool isTileValue() const
Return true if this iterator is currently pointing to a (non-leaf) tile value.
Definition: TreeIterator.h:685
GLuint GLfloat * val
Definition: glcorearb.h:1608
bool next()
Advance the iterator to the next leaf node.
void modifyValue(const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing. (Not valid for const iterators...
Definition: TreeIterator.h:713
IteratorRange & operator++()
Advance the iterator to the next item.
typename PrevItem::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:218
typename CopyConstness< RootNodeT, NCLeafNodeT >::Type LeafNodeT
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:679
IteratorRange(IteratorRange &other, tbb::split)
Split constructor used by tbb (should rarely be called directly)
void setValue(const ValueT &val) const
Change the tile or voxel value to which this iterator is currently pointing and mark it as active...
Definition: TreeIterator.h:700
void increment(size_t n=1)
Advance the iterator n times.
void modifyValue(Index lvl, const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing.
Definition: TreeIterator.h:362
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:521
void OIIO_UTIL_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
void increment(Index n)
Increment the iterator n times.
An IterListItem is an element of a compile-time linked list of iterators to nodes of different types...
Definition: TreeIterator.h:214
typename RootIterT::NonConstNodeType NCRootNodeT
typename CopyConstness< NodeT, typename NodeT::ChildNodeType >::Type ChildT
NodeT's child node type, with the same constness (e.g., const InternalNode<...>)
Definition: TreeIterator.h:232
LeafNodeT * getLeaf() const
Return the leaf node to which the iterator is pointing.
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:119
TreeT * getTree() const
Return a pointer to the tree over which this iterator is iterating.
Definition: TreeIterator.h:716
A list of types (not necessarily unique)
Definition: TypeList.h:577
static const Index Level
NodeT's level in its tree (0 = LeafNode)
Definition: TreeIterator.h:237
typename InvTreeT::Front _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:220
static ChildT * getChild(const IterT &)
Definition: TreeIterator.h:62
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:787
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:657
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
void setValueOff(Index lvl) const
Mark the value to which the iterator at level lvl of the tree points as inactive. ...
Definition: TreeIterator.h:354
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:660
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:962
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:566