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