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