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: 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)
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)
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)
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 
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;
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  }
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
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:640
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:671
std::string summary() const
Return a string (for debugging, mainly) describing this iterator's current state. ...
Definition: TreeIterator.h:908
const NCValueT & getValue(Index lvl) const
Return the value to which the iterator at level lvl of the tree points.
Definition: TreeIterator.h:330
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:957
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
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
GLsizeiptr size
Definition: glew.h:1681
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:296
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:943
bool is_divisible() const
Return true if this range is splittable (i.e., if the iterator can be advanced more than mGrainSize t...
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
bool next()
Advance to the next tile or voxel value. Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:805
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:980
LeafNodeT & operator*() const
Return the leaf node to which the iterator is pointing.
GLuint const GLfloat * val
Definition: glew.h:2794
typename SubtreeT::template Append< HeadT > Type
Definition: TreeIterator.h:34
void setValueOff() const
Mark the tile or voxel value to which this iterator is currently pointing as inactive.
Definition: TreeIterator.h:704
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:636
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT's child node type with const qualifiers removed.
Definition: TreeIterator.h:233
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:935
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:166
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:524
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 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:259
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
bool isValueOn() const
Return true if the value to which this iterator is currently pointing is active.
Definition: TreeIterator.h:688
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:392
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:518
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
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
TreeValueIteratorBase & operator++()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:652
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:394
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:225
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:227
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
const ValueT & operator*() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:693
void increment(Index n)
Increment the iterator n times.
Definition: TreeIterator.h:976
NodeIteratorBase & operator=(const NodeIteratorBase &other)
void OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
Index64 getVoxelCount(Index lvl) const
Return the number of (virtual) voxels spanned by a tile value or child node.
Definition: TreeIterator.h:318
bool next()
Advance the iterator to the next item.
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:941
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
const ValueT & getValue() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:692
*But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:639
TreeValueIteratorBase & operator=(const TreeValueIteratorBase &other)
Definition: TreeIterator.h:768
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:965
typename std::remove_const< ToType >::type Type
Definition: Types.h:298
void increment(Index n=1)
Advance the iterator n times.
void
Definition: png.h:1083
const ValueT * operator->() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:694
GLsizei n
Definition: glew.h:4040
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:644
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
typename IterT::NodeType NodeT
The type of node over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:516
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:390
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
typename CopyConstness< NodeT, typename NodeT::ChildNodeType >::Type ChildT
NodeT's child node type, with the same constness (e.g., const InternalNode<...>)
Definition: TreeIterator.h:522
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
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:33
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
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
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:510
typename ValueIterT::NonConstValueType ValueT
Definition: TreeIterator.h:622
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:242
typename NodeVecT::Front _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:384
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:681
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
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:686
void getNode(Index lvl, OtherNodeT *&node) const
Return the node over which one of the following list elements' iterator iterates. ...
Definition: TreeIterator.h:265
LeafIteratorBase & operator++()
Advance the iterator to the next leaf node.
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLsizei const GLchar *const * string
Definition: glew.h:1844
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:382
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:229
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
Index pos(Index lvl) const
Return The table offset of the iterator at level lvl of the tree.
Definition: TreeIterator.h:286
bool next(Index lvl)
Increment the iterator at level lvl of the tree.
Definition: TreeIterator.h:292
IteratorRange(const IterT &iter, size_t grainSize=8)
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:973
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
bool next()
Advance to the next tile or voxel value.
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:616
bool isTileValue() const
Return true if this iterator is currently pointing to a (non-leaf) tile value.
Definition: TreeIterator.h:684
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:712
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:217
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:678
IteratorRange(IteratorRange &other, tbb::split)
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
void modifyValue(Index lvl, const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing.
Definition: TreeIterator.h:361
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:520
void increment(Index n)
Increment the iterator n times.
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
An IterListItem is an element of a compile-time linked list of iterators to nodes of different types...
Definition: TreeIterator.h:213
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:231
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:112
TreeT * getTree() const
Return a pointer to the tree over which this iterator is iterating.
Definition: TreeIterator.h:715
A list of types (not necessarily unique)
Definition: Types.h:652
static const Index Level
NodeT's level in its tree (0 = LeafNode)
Definition: TreeIterator.h:236
typename InvTreeT::Front _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:219
static ChildT * getChild(const IterT &)
Definition: TreeIterator.h:61
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
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
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: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:659
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:961