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