OpenVDB  0.104.0
TreeIterator.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012 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 //
30 //
32 
33 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
34 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
35 
36 #include <boost/mpl/front.hpp>
37 #include <boost/mpl/pop_front.hpp>
38 #include <boost/mpl/push_back.hpp>
39 #include <boost/mpl/size.hpp>
40 #include <boost/mpl/vector.hpp>
41 #include <boost/static_assert.hpp>
42 #include <boost/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 
65 template<typename FromType, typename ToType> struct CopyConstness {
66  typedef typename boost::remove_const<ToType>::type Type;
67 };
68 template<typename FromType, typename ToType> struct CopyConstness<const FromType, ToType> {
69  typedef const ToType Type;
70 };
71 
72 
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;
81  typedef typename boost::mpl::push_back<SubtreeT, HeadT>::type Type;
82 };
83 template<typename HeadT>
84 struct InvertedTree<HeadT, /*HeadLevel=*/1> {
85  typedef typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type Type;
86 };
87 
88 } // namespace iter
89 
90 
92 
93 
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 
247 
248 
259 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level>
261 {
262 public:
264  typedef typename PrevItemT::IterT PrevIterT;
266  typedef typename boost::mpl::front<NodeVecT>::type _NodeT;
269  NodeConverter<_NodeT>::Type IterT;
270 
272  typedef typename IterT::NodeType NodeT;
274  typedef typename IterT::NonConstNodeType NCNodeT;
276  typedef typename IterT::NonConstValueType NCValueT;
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) {}
288  IterListItem& operator=(const IterListItem& other)
289  {
290  if (&other != this) {
291  mIter = other.mIter;
292  mNext = other.mNext;
293  mPrev = NULL;
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 
305  void getNode(Index lvl, NodeT*& node) const
306  {
307  node = (lvl <= Level) ? mIter.getParentNode() : NULL;
308  }
310  template<typename OtherNodeT>
311  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
312 
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 
332  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
333 
335  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
336 
338  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
339 
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 
355  Coord getCoord(Index lvl) const
356  {
357  return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
358  }
359  Index getChildDim(Index lvl) const
360  {
361  return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
362  }
364  Index64 getVoxelCount(Index lvl) const
365  {
366  return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
367  }
368 
370  bool isValueOn(Index lvl) const
371  {
372  return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
373  }
374 
376  const NCValueT& getValue(Index lvl) const
377  {
378  if (lvl == Level) return mIter.getValue();
379  return mNext.getValue(lvl);
380  }
381 
385  void setValue(Index lvl, const NCValueT& val) const
386  {
387  if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val);
388  }
392  void setValueOn(Index lvl, bool on = true) const
393  {
394  if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
395  }
399  void setValueOff(Index lvl) const
400  {
401  if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl);
402  }
403 
404 private:
405  typedef typename boost::mpl::pop_front<NodeVecT>::type RestT; // NodeVecT minus its first item
406  typedef IterListItem<IterListItem, RestT, VecSize - 1, Level + 1> NextItem;
407 
408  IterT mIter;
409  NextItem mNext;
410  PrevItemT* mPrev;
411 };
412 
413 
415 template<typename PrevItemT, typename NodeVecT, size_t VecSize>
416 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U>
417 {
418 public:
420  typedef typename PrevItemT::IterT PrevIterT;
422  typedef typename boost::mpl::front<NodeVecT>::type _NodeT;
425  NodeConverter<_NodeT>::Type IterT;
426 
428  typedef typename IterT::NodeType NodeT;
430  typedef typename IterT::NonConstNodeType NCNodeT;
432  typedef typename IterT::NonConstValueType NCValueT;
435  static const Index Level = 0;
436 
437  IterListItem(PrevItemT*): mNext(this), mPrev(NULL) {}
438 
439  IterListItem(const IterListItem& other): mIter(other.mIter), mNext(other.mNext), mPrev(NULL) {}
440  IterListItem& operator=(const IterListItem& other)
441  {
442  if (&other != this) {
443  mIter = other.mIter;
444  mNext = other.mNext;
445  mPrev = NULL;
446  }
447  return *this;
448  }
449 
450  void updateBackPointers(PrevItemT* = NULL) { mPrev = NULL; mNext.updateBackPointers(this); }
451 
452  void setIter(const IterT& iter) { mIter = iter; }
453  template<typename OtherIterT>
454  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
455 
456  void getNode(Index lvl, NodeT*& node) const
457  {
458  node = (lvl == 0) ? mIter.getParentNode() : NULL;
459  }
460  template<typename OtherNodeT>
461  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
462 
463  template<typename OtherIterListItemT>
464  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
465  {
466  if (lvl == 0) {
467  const NodeT* node = NULL;
468  otherListItem.getNode(lvl, node);
469  mIter = (node == NULL) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
470  } else {
471  mNext.initLevel(lvl, otherListItem);
472  }
473  }
474 
475  Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
476 
477  bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
478 
479  bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
480 
481  bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); }
482 
483  Coord getCoord(Index lvl) const
484  {
485  return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
486  }
487  Index getChildDim(Index lvl) const
488  {
489  return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
490  }
491 
492  Index64 getVoxelCount(Index lvl) const
493  {
494  return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
495  }
496 
497  bool isValueOn(Index lvl) const
498  {
499  return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
500  }
501 
502  const NCValueT& getValue(Index lvl) const
503  {
504  if (lvl == 0) return mIter.getValue();
505  return mNext.getValue(lvl);
506  }
507 
508  void setValue(Index lvl, const NCValueT& val) const
509  {
510  if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val);
511  }
512  void setValueOn(Index lvl, bool on = true) const
513  {
514  if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
515  }
516  void setValueOff(Index lvl) const
517  {
518  if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl);
519  }
520 
521 private:
522  typedef typename boost::mpl::pop_front<NodeVecT>::type RestT; // NodeVecT minus its first item
523  typedef IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1> NextItem;
524 
525  IterT mIter;
526  NextItem mNext;
527  PrevItemT* mPrev;
528 };
529 
530 
532 template<typename PrevItemT, typename NodeVecT, Index _Level>
533 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level>
534 {
535 public:
536  typedef typename boost::mpl::front<NodeVecT>::type _NodeT;
538  typedef typename PrevItemT::IterT PrevIterT;
541  NodeConverter<_NodeT>::Type IterT;
542 
544  typedef typename IterT::NodeType NodeT;
546  typedef typename IterT::NonConstNodeType NCNodeT;
548  typedef typename IterT::NonConstValueType NCValueT;
555  static const Index Level = _Level;
556 
557  IterListItem(PrevItemT* prev): mPrev(prev) {}
558 
559  IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(NULL) {}
560  IterListItem& operator=(const IterListItem& other)
561  {
562  if (&other != this) {
563  mIter = other.mIter;
564  mPrev = NULL;
565  }
566  return *this;
567  }
568 
569  void updateBackPointers(PrevItemT* prev) { mPrev = prev; }
570 
571  // The following method specializations differ from the default template
572  // implementations mainly in that they don't forward.
573 
574  void setIter(const IterT& iter) { mIter = iter; }
575 
576  void getNode(Index lvl, NodeT*& node) const
577  {
578  node = (lvl <= Level) ? mIter.getParentNode() : NULL;
579  }
580 
581  template<typename OtherIterListItemT>
582  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
583  {
584  if (lvl == Level) {
585  const NodeT* node = NULL;
586  otherListItem.getNode(lvl, node);
587  mIter = (node == NULL) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
588  }
589  }
590 
591  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); }
592 
593  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; }
594 
595  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; }
596 
597  bool down(Index lvl)
598  {
599  if (lvl == Level && mPrev != NULL && mIter) {
600  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
601  mPrev->setIter(PrevItemT::ITraits::begin(*child));
602  return true;
603  }
604  }
605  return false;
606  }
607 
608  Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); }
609  Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; }
610  Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; }
611 
612  bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; }
613 
614  const NCValueT& getValue(Index lvl) const
615  {
616  assert(lvl == Level);
617  (void)lvl; // avoid unused variable warning in optimized builds
618  return mIter.getValue();
619  }
620 
621  void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); }
622  void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); }
623  void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); }
624 
625 private:
626  IterT mIter;
627  PrevItemT* mPrev;
628 };
629 
630 
632 
633 
634 //#define DEBUG_TREE_VALUE_ITERATOR
635 
637 template<typename _TreeT, typename ValueIterT>
639 {
640 public:
641  typedef _TreeT TreeT;
642  typedef typename ValueIterT::NodeType NodeT;
643  typedef typename ValueIterT::NonConstValueType ValueT;
644  typedef typename NodeT::ChildOnCIter ChildOnIterT;
645  static const Index ROOT_LEVEL = NodeT::LEVEL;
646  BOOST_STATIC_ASSERT(ValueIterT::NodeType::LEVEL == ROOT_LEVEL);
647  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
648 
650 
652  TreeValueIteratorBase& operator=(const TreeValueIteratorBase& other);
653 
655  void setMinDepth(Index minDepth);
657  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
659  void setMaxDepth(Index maxDepth);
661  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
662 
664 
665  bool test() const { return mValueIterList.test(mLevel); }
666  operator bool() const { return this->test(); }
668 
671  bool next();
673  TreeValueIteratorBase& operator++() { this->next(); return *this; }
674 
677  Index getLevel() const { return mLevel; }
680  Index getDepth() const { return ROOT_LEVEL - mLevel; }
681  static Index getLeafDepth() { return LEAF_DEPTH; }
682 
687  template<typename NodeType>
688  void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); }
689 
692  Coord getCoord() const { return mValueIterList.getCoord(mLevel); }
696  bool getBoundingBox(CoordBBox&) const;
699  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
700 
702  Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);}
703 
705  bool isTileValue() const { return mLevel != 0 && this->test(); }
707  bool isVoxelValue() const { return mLevel == 0 && this->test(); }
709  bool isValueOn() const { return mValueIterList.isValueOn(mLevel); }
710 
712 
713  const ValueT& getValue() const { return mValueIterList.getValue(mLevel); }
714  const ValueT& operator*() const { return this->getValue(); }
715  const ValueT* operator->() const { return &(this->operator*()); }
717 
720  void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); }
722 
723 
724  void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); }
726  OPENVDB_DEPRECATED void setValueOn(bool on=true) const {mValueIterList.setValueOn(mLevel,on);}
728 
729  void setValueOff() const { mValueIterList.setValueOff(mLevel); }
730 
732  TreeT* getTree() const { return mTree; }
733 
735  std::string summary() const;
736 
737 private:
738  bool advance(bool dontIncrement = false);
739 
740  typedef typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type InvTreeT;
741  struct PrevChildItem { typedef ChildOnIterT IterT; };
742  struct PrevValueItem { typedef ValueIterT IterT; };
743 
744  IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList;
745  IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList;
746  Index mLevel;
747  int mMinLevel, mMaxLevel;
748  TreeT* mTree;
749 }; // class TreeValueIteratorBase
750 
751 
752 template<typename TreeT, typename ValueIterT>
753 inline
755  mChildIterList(NULL),
756  mValueIterList(NULL),
757  mLevel(ROOT_LEVEL),
758  mMinLevel(int(LEAF_LEVEL)),
759  mMaxLevel(int(ROOT_LEVEL)),
760  mTree(&tree)
761 {
762  mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.getRootNode()));
763  mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.getRootNode()));
764  this->advance(/*dontIncrement=*/true);
765 }
766 
767 
768 template<typename TreeT, typename ValueIterT>
769 inline
771  mChildIterList(other.mChildIterList),
772  mValueIterList(other.mValueIterList),
773  mLevel(other.mLevel),
774  mMinLevel(other.mMinLevel),
775  mMaxLevel(other.mMaxLevel),
776  mTree(other.mTree)
777 {
778  mChildIterList.updateBackPointers();
779  mValueIterList.updateBackPointers();
780 }
781 
782 
783 template<typename TreeT, typename ValueIterT>
786 {
787  if (&other != this) {
788  mChildIterList = other.mChildIterList;
789  mValueIterList = other.mValueIterList;
790  mLevel = other.mLevel;
791  mMinLevel = other.mMinLevel;
792  mMaxLevel = other.mMaxLevel;
793  mTree = other.mTree;
794  mChildIterList.updateBackPointers();
795  mValueIterList.updateBackPointers();
796  }
797  return *this;
798 }
799 
800 
801 template<typename TreeT, typename ValueIterT>
802 inline void
804 {
805  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
806  if (int(mLevel) > mMaxLevel) this->next();
807 }
808 
809 
810 template<typename TreeT, typename ValueIterT>
811 inline void
813 {
814  // level = ROOT_LEVEL - depth
815  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
816  if (int(mLevel) < mMinLevel) this->next();
817 }
818 
819 
820 template<typename TreeT, typename ValueIterT>
821 inline bool
823 {
824  do {
825  if (!this->advance()) return false;
826  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
827  return true;
828 }
829 
830 
831 template<typename TreeT, typename ValueIterT>
832 inline bool
834 {
835  Index
836  vPos = mValueIterList.pos(mLevel),
837  cPos = mChildIterList.pos(mLevel);
838  if (vPos == cPos && mChildIterList.test(mLevel)) {
840  mValueIterList.next(mLevel);
841  vPos = mValueIterList.pos(mLevel);
842  }
843  if (vPos < cPos) {
844  if (dontIncrement) return true;
845  if (mValueIterList.next(mLevel)) {
846  if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
848  mValueIterList.next(mLevel);
849  }
850  // If there is a next value and it precedes the next child, return.
851  if (mValueIterList.pos(mLevel) < cPos) return true;
852  }
853  } else {
854  // Advance to the next child, which may or may not precede the next value.
855  if (!dontIncrement) mChildIterList.next(mLevel);
856  }
857 #ifdef DEBUG_TREE_VALUE_ITERATOR
858  std::cout << "\n" << this->summary() << std::flush;
859 #endif
860 
861  // Descend to the lowest level at which the next value precedes the next child.
862  while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
863 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
864  if (int(mLevel) == mMinLevel) {
865  // If the current node lies at the lowest allowed level, none of its
866  // children can be visited, so advance its child iterator to the end.
869  while (mChildIterList.test(mLevel)) mChildIterList.next(mLevel);
870  } else
871 #endif
872  if (mChildIterList.down(mLevel)) {
873  --mLevel; // descend one level
874  mValueIterList.initLevel(mLevel, mChildIterList);
875  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
876  && mChildIterList.test(mLevel))
877  {
879  mValueIterList.next(mLevel);
880  }
881  } else break;
882 #ifdef DEBUG_TREE_VALUE_ITERATOR
883  std::cout << "\n" << this->summary() << std::flush;
884 #endif
885  }
886  // Ascend to the nearest level at which one of the iterators is not yet exhausted.
887  while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
888  if (mLevel == ROOT_LEVEL) return false;
889  ++mLevel;
890  mChildIterList.next(mLevel);
891  this->advance(/*dontIncrement=*/true);
892  }
893  return true;
894 }
895 
896 
897 template<typename TreeT, typename ValueIterT>
898 inline bool
900 {
901  if (!this->test()) {
902  bbox = CoordBBox();
903  return false;
904  }
905  bbox.min() = mValueIterList.getCoord(mLevel);
906  bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1);
907  return true;
908 }
909 
910 
911 template<typename TreeT, typename ValueIterT>
912 inline std::string
914 {
915  std::ostringstream ostr;
916  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
917  if (lvl == 0) ostr << "leaf";
918  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
919  else ostr << "int" << (ROOT_LEVEL - lvl);
920  ostr << " v" << mValueIterList.pos(lvl)
921  << " c" << mChildIterList.pos(lvl);
922  if (lvl > int(mLevel)) ostr << " / ";
923  }
924  if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
925  if (mLevel == 0) {
926  ostr << " " << this->getCoord();
927  } else {
928  ostr << " " << this->getBoundingBox();
929  }
930  }
931  return ostr.str();
932 }
933 
934 
936 
937 
939 template<typename _TreeT, typename RootChildOnIterT>
941 {
942 public:
943  typedef _TreeT TreeT;
944  typedef RootChildOnIterT RootIterT;
945  typedef typename RootIterT::NodeType RootNodeT;
946  typedef typename RootIterT::NonConstNodeType NCRootNodeT;
947  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
949  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
950 
952 
955 
956  NodeIteratorBase(const NodeIteratorBase& other);
958 
960  void setMinDepth(Index minDepth);
962  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
964  void setMaxDepth(Index maxDepth);
966  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
967 
969 
970  bool test() const { return !mDone; }
971  operator bool() const { return this->test(); }
973 
976  bool next();
978  void increment() { this->next(); }
979  NodeIteratorBase& operator++() { this->increment(); return *this; }
981  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
982 
985  Index getLevel() const { return mLevel; }
988  Index getDepth() const { return ROOT_LEVEL - mLevel; }
989  static Index getLeafDepth() { return LEAF_DEPTH; }
990 
993  Coord getCoord() const;
997  bool getBoundingBox(CoordBBox& bbox) const;
1000  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
1001 
1005  template<typename NodeT>
1006  void getNode(NodeT*& node) const { node = NULL; mIterList.getNode(mLevel, node); }
1007 
1008  TreeT* getTree() const { return mTree; }
1009 
1010  std::string summary() const;
1011 
1012 private:
1013  struct PrevItem { typedef RootIterT IterT; };
1014 
1015  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1016  Index mLevel;
1017  int mMinLevel, mMaxLevel;
1018  bool mDone;
1019  TreeT* mTree;
1020 }; // class NodeIteratorBase
1021 
1022 
1023 template<typename TreeT, typename RootChildOnIterT>
1024 inline
1026  mIterList(NULL),
1027  mLevel(ROOT_LEVEL),
1028  mMinLevel(int(LEAF_LEVEL)),
1029  mMaxLevel(int(ROOT_LEVEL)),
1030  mDone(true),
1031  mTree(NULL)
1032 {
1033 }
1034 
1035 
1036 template<typename TreeT, typename RootChildOnIterT>
1037 inline
1039  mIterList(NULL),
1040  mLevel(ROOT_LEVEL),
1041  mMinLevel(int(LEAF_LEVEL)),
1042  mMaxLevel(int(ROOT_LEVEL)),
1043  mDone(false),
1044  mTree(&tree)
1045 {
1046  mIterList.setIter(RootIterTraits::begin(tree.getRootNode()));
1047 }
1048 
1049 
1050 template<typename TreeT, typename RootChildOnIterT>
1051 inline
1053  mIterList(other.mIterList),
1054  mLevel(other.mLevel),
1055  mMinLevel(other.mMinLevel),
1056  mMaxLevel(other.mMaxLevel),
1057  mDone(other.mDone),
1058  mTree(other.mTree)
1059 {
1060  mIterList.updateBackPointers();
1061 }
1062 
1063 
1064 template<typename TreeT, typename RootChildOnIterT>
1067 {
1068  if (&other != this) {
1069  mLevel = other.mLevel;
1070  mMinLevel = other.mMinLevel;
1071  mMaxLevel = other.mMaxLevel;
1072  mDone = other.mDone;
1073  mTree = other.mTree;
1074  mIterList = other.mIterList;
1075  mIterList.updateBackPointers();
1076  }
1077  return *this;
1078 }
1079 
1080 
1081 template<typename TreeT, typename RootChildOnIterT>
1082 inline void
1084 {
1085  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
1086  if (int(mLevel) > mMaxLevel) this->next();
1087 }
1088 
1089 
1090 template<typename TreeT, typename RootChildOnIterT>
1091 inline void
1093 {
1094  // level = ROOT_LEVEL - depth
1095  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
1096  if (int(mLevel) < mMinLevel) this->next();
1097 }
1098 
1099 
1100 template<typename TreeT, typename RootChildOnIterT>
1101 inline bool
1103 {
1104  do {
1105  if (mDone) return false;
1106 
1107  // If the iterator over the current node points to a child,
1108  // descend to the child (depth-first traversal).
1109  if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1110  if (!mIterList.down(mLevel)) return false;
1111  --mLevel;
1112  } else {
1113  // Ascend to the nearest ancestor that has other children.
1114  while (!mIterList.test(mLevel)) {
1115  if (mLevel == ROOT_LEVEL) {
1116  // Can't ascend higher than the root.
1117  mDone = true;
1118  return false;
1119  }
1120  ++mLevel; // ascend one level
1121  mIterList.next(mLevel); // advance to the next child, if there is one
1122  }
1123  // Descend to the child.
1124  if (!mIterList.down(mLevel)) return false;
1125  --mLevel;
1126  }
1127  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1128  return true;
1129 }
1130 
1131 
1132 template<typename TreeT, typename RootChildOnIterT>
1133 inline Coord
1135 {
1136  if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1);
1137  RootNodeT* root = NULL;
1138  this->getNode(root);
1139  return root ? root->getMinIndex() : Coord::min();
1140 }
1141 
1142 
1143 template<typename TreeT, typename RootChildOnIterT>
1144 inline bool
1146 {
1147  if (mLevel == ROOT_LEVEL) {
1148  RootNodeT* root = NULL;
1149  this->getNode(root);
1150  if (root == NULL) {
1151  bbox = CoordBBox();
1152  return false;
1153  }
1154  root->getIndexRange(bbox);
1155  return true;
1156  }
1157  bbox.min() = mIterList.getCoord(mLevel + 1);
1158  bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1159  return true;
1160 }
1161 
1162 
1163 template<typename TreeT, typename RootChildOnIterT>
1164 inline std::string
1166 {
1167  std::ostringstream ostr;
1168  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1169  if (lvl == 0) ostr << "leaf";
1170  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
1171  else ostr << "int" << (ROOT_LEVEL - lvl);
1172  ostr << " c" << mIterList.pos(lvl);
1173  if (lvl > int(mLevel)) ostr << " / ";
1174  }
1175  CoordBBox bbox;
1176  this->getBoundingBox(bbox);
1177  ostr << " " << bbox;
1178  return ostr.str();
1179 }
1180 
1181 
1183 
1184 
1186 template<typename TreeT, typename RootChildOnIterT>
1188 {
1189 public:
1190  typedef RootChildOnIterT RootIterT;
1191  typedef typename RootIterT::NodeType RootNodeT;
1192  typedef typename RootIterT::NonConstNodeType NCRootNodeT;
1193  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
1195  typedef typename boost::mpl::front<InvTreeT>::type NCLeafNodeT;
1198 
1200 
1201  LeafIteratorBase(): mIterList(NULL), mTree(NULL) {}
1202 
1203  LeafIteratorBase(TreeT& tree): mIterList(NULL), mTree(&tree)
1204  {
1205  // Initialize the iterator list with a root node iterator.
1206  mIterList.setIter(RootIterTraits::begin(tree.getRootNode()));
1207  // Descend along the first branch, initializing the node iterator at each level.
1208  Index lvl = ROOT_LEVEL;
1209  for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {}
1210  // If the first branch terminated above the leaf level, backtrack to the next branch.
1211  if (lvl > 0) this->next();
1212  }
1213 
1214  LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree)
1215  {
1216  mIterList.updateBackPointers();
1217  }
1219  {
1220  if (&other != this) {
1221  mTree = other.mTree;
1222  mIterList = other.mIterList;
1223  mIterList.updateBackPointers();
1224  }
1225  return *this;
1226  }
1227 
1229 
1230  LeafNodeT* getLeaf() const { LeafNodeT* n = NULL; mIterList.getNode(LEAF_LEVEL, n); return n; }
1231  LeafNodeT& operator*() const { return *this->getLeaf(); }
1232  LeafNodeT* operator->() const { return this->getLeaf(); }
1234 
1235  bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); }
1236  operator bool() const { return this->test(); }
1237 
1239 
1240  bool next();
1241  void increment() { this->next(); }
1242  LeafIteratorBase& operator++() { this->increment(); return *this; }
1244 
1245  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1246 
1247  TreeT* getTree() const { return mTree; }
1248 
1249 private:
1250  struct PrevItem { typedef RootIterT IterT; };
1251 
1255  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1256  TreeT* mTree;
1257 }; // class LeafIteratorBase
1258 
1259 
1260 template<typename TreeT, typename RootChildOnIterT>
1261 inline bool
1263 {
1264  // If the iterator is valid for the current node one level above the leaf level,
1265  // advance the iterator to the node's next child.
1266  if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1267  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1268  return true;
1269  }
1270 
1271  Index lvl = LEAF_PARENT_LEVEL;
1272  while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1273  if (mIterList.test(lvl)) {
1274  mIterList.next(lvl);
1275  } else {
1276  do {
1277  // Ascend to the nearest level at which
1278  // one of the iterators is not yet exhausted.
1279  if (lvl == ROOT_LEVEL) return false;
1280  ++lvl;
1281  if (mIterList.test(lvl)) mIterList.next(lvl);
1282  } while (!mIterList.test(lvl));
1283  }
1284  // Descend to the lowest child, but not as far as the leaf iterator.
1285  while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1286  }
1287  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1288  return true;
1289 }
1290 
1291 
1293 
1294 
1297 template<typename IterT>
1299 {
1300 public:
1301  IteratorRange(const IterT& iter, size_t grainSize = 8):
1302  mIter(iter),
1303  mGrainSize(grainSize),
1304  mSize(0)
1305  {
1306  mSize = this->size();
1307  }
1308  IteratorRange(IteratorRange& other, tbb::split):
1309  mIter(other.mIter),
1310  mGrainSize(other.mGrainSize),
1311  mSize(other.mSize >> 1)
1312  {
1313  other.increment(mSize);
1314  }
1315 
1319  const IterT& iterator() const { return mIter; }
1320 
1321  bool empty() const { return mSize == 0 || !mIter.test(); }
1322  bool test() const { return !this->empty(); }
1323  operator bool() const { return !this->empty(); }
1324 
1327  bool is_divisible() const { return mSize > mGrainSize; }
1328 
1330  void increment(Index n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1332  IteratorRange& operator++() { this->increment(); return *this; }
1335  bool next() { this->increment(); return this->test(); }
1336 
1337 private:
1338  Index size() const { Index n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; }
1339 
1340  IterT mIter;
1341  size_t mGrainSize;
1346  Index mSize;
1347 };
1348 
1349 
1351 
1352 
1355 
1356 } // namespace tree
1357 } // namespace OPENVDB_VERSION_NAME
1358 } // namespace openvdb
1359 
1360 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
1361 
1362 // Copyright (c) 2012 DreamWorks Animation LLC
1363 // All rights reserved. This software is distributed under the
1364 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )