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