OpenVDB  4.0.2
NodeMasks.h
Go to the documentation of this file.
1 //
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 //
30 //
34 
35 #ifndef OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
36 #define OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
37 
38 #include <cassert>
39 #include <cstring>
40 #include <iostream>// for cout
41 #include <openvdb/Platform.h>
42 #include <openvdb/Types.h>
43 //#include <boost/mpl/if.hpp>
44 //#include <strings.h> // for ffs
45 
46 namespace openvdb {
48 namespace OPENVDB_VERSION_NAME {
49 namespace util {
50 
52 inline Index32
54 {
55  // Simple LUT:
56 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
57  static
58 #endif
59  const Byte numBits[256] = {
61 #define COUNTONB2(n) n, n+1, n+1, n+2
62 #define COUNTONB4(n) COUNTONB2(n), COUNTONB2(n+1), COUNTONB2(n+1), COUNTONB2(n+2)
63 #define COUNTONB6(n) COUNTONB4(n), COUNTONB4(n+1), COUNTONB4(n+1), COUNTONB4(n+2)
64  COUNTONB6(0), COUNTONB6(1), COUNTONB6(1), COUNTONB6(2)
65  };
66  return numBits[v];
67 #undef COUNTONB6
68 #undef COUNTONB4
69 #undef COUNTONB2
70 
71  // Sequentially clear least significant bits
72  //Index32 c;
73  //for (c = 0; v; c++) v &= v - 0x01U;
74  //return c;
75 
76  // This version is only fast on CPUs with fast "%" and "*" operations
77  //return (v * UINT64_C(0x200040008001) & UINT64_C(0x111111111111111)) % 0xF;
78 }
79 
81 inline Index32 CountOff(Byte v) { return CountOn(static_cast<Byte>(~v)); }
82 
84 inline Index32
86 {
87  v = v - ((v >> 1) & 0x55555555U);
88  v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
89  return (((v + (v >> 4)) & 0xF0F0F0FU) * 0x1010101U) >> 24;
90 }
91 
93 inline Index32 CountOff(Index32 v) { return CountOn(~v); }
94 
96 inline Index32
98 {
99  v = v - ((v >> 1) & UINT64_C(0x5555555555555555));
100  v = (v & UINT64_C(0x3333333333333333)) + ((v >> 2) & UINT64_C(0x3333333333333333));
101  return static_cast<Index32>(
102  (((v + (v >> 4)) & UINT64_C(0xF0F0F0F0F0F0F0F)) * UINT64_C(0x101010101010101)) >> 56);
103 }
104 
106 inline Index32 CountOff(Index64 v) { return CountOn(~v); }
107 
109 inline Index32
111 {
112  assert(v);
113 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
114  static
115 #endif
116  const Byte DeBruijn[8] = {0, 1, 6, 2, 7, 5, 4, 3};
117  return DeBruijn[Byte((v & -v) * 0x1DU) >> 5];
118 }
119 
121 inline Index32
123 {
124  assert(v);
125  //return ffs(v);
126 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
127  static
128 #endif
129  const Byte DeBruijn[32] = {
130  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
131  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
132  };
133  return DeBruijn[Index32((v & -v) * 0x077CB531U) >> 27];
134 }
135 
137 inline Index32
139 {
140  assert(v);
141  //return ffsll(v);
142 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
143  static
144 #endif
145  const Byte DeBruijn[64] = {
146  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
147  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
148  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
149  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12,
150  };
151  return DeBruijn[Index64((v & -v) * UINT64_C(0x022FDD63CC95386D)) >> 58];
152 }
153 
155 inline Index32
157 {
158 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
159  static
160 #endif
161  const Byte DeBruijn[32] = {
162  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
163  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
164  };
165  v |= v >> 1; // first round down to one less than a power of 2
166  v |= v >> 2;
167  v |= v >> 4;
168  v |= v >> 8;
169  v |= v >> 16;
170  return DeBruijn[Index32(v * 0x07C4ACDDU) >> 27];
171 }
172 
173 
175 
176 
178 template<typename NodeMask>
180 {
181 protected:
182  Index32 mPos; // bit position
183  const NodeMask* mParent; // this iterator can't change the parent_mask!
184 
185 public:
186  BaseMaskIterator(): mPos(NodeMask::SIZE), mParent(nullptr) {}
187  BaseMaskIterator(const BaseMaskIterator&) = default;
188  BaseMaskIterator(Index32 pos, const NodeMask* parent): mPos(pos), mParent(parent)
189  {
190  assert((parent == nullptr && pos == 0) || (parent != nullptr && pos <= NodeMask::SIZE));
191  }
192  bool operator==(const BaseMaskIterator &iter) const {return mPos == iter.mPos;}
193  bool operator!=(const BaseMaskIterator &iter) const {return mPos != iter.mPos;}
194  bool operator< (const BaseMaskIterator &iter) const {return mPos < iter.mPos;}
196  {
197  mPos = iter.mPos; mParent = iter.mParent; return *this;
198  }
199  Index32 offset() const { return mPos; }
200  Index32 pos() const { return mPos; }
201  bool test() const { assert(mPos <= NodeMask::SIZE); return (mPos != NodeMask::SIZE); }
202  operator bool() const { return this->test(); }
203 }; // class BaseMaskIterator
204 
205 
207 template <typename NodeMask>
208 class OnMaskIterator: public BaseMaskIterator<NodeMask>
209 {
210 private:
212  using BaseType::mPos;//bit position;
213  using BaseType::mParent;//this iterator can't change the parent_mask!
214 public:
215  OnMaskIterator() : BaseType() {}
216  OnMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
217  void increment()
218  {
219  assert(mParent != nullptr);
220  mPos = mParent->findNextOn(mPos+1);
221  assert(mPos <= NodeMask::SIZE);
222  }
223  void increment(Index n) { while(n-- && this->next()) ; }
224  bool next()
225  {
226  this->increment();
227  return this->test();
228  }
229  bool operator*() const {return true;}
231  {
232  this->increment();
233  return *this;
234  }
235 }; // class OnMaskIterator
236 
237 
238 template <typename NodeMask>
239 class OffMaskIterator: public BaseMaskIterator<NodeMask>
240 {
241 private:
243  using BaseType::mPos;//bit position;
244  using BaseType::mParent;//this iterator can't change the parent_mask!
245 public:
246  OffMaskIterator() : BaseType() {}
247  OffMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
248  void increment()
249  {
250  assert(mParent != nullptr);
251  mPos=mParent->findNextOff(mPos+1);
252  assert(mPos <= NodeMask::SIZE);
253  }
254  void increment(Index n) { while(n-- && this->next()) ; }
255  bool next()
256  {
257  this->increment();
258  return this->test();
259  }
260  bool operator*() const {return false;}
262  {
263  this->increment();
264  return *this;
265  }
266 }; // class OffMaskIterator
267 
268 
269 template <typename NodeMask>
270 class DenseMaskIterator: public BaseMaskIterator<NodeMask>
271 {
272 private:
274  using BaseType::mPos;//bit position;
275  using BaseType::mParent;//this iterator can't change the parent_mask!
276 
277 public:
278  DenseMaskIterator() : BaseType() {}
279  DenseMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
280  void increment()
281  {
282  assert(mParent != nullptr);
283  mPos += 1;//careful - the increment might go beyond the end
284  assert(mPos<= NodeMask::SIZE);
285  }
286  void increment(Index n) { while(n-- && this->next()) ; }
287  bool next()
288  {
289  this->increment();
290  return this->test();
291  }
292  bool operator*() const {return mParent->isOn(mPos);}
294  {
295  this->increment();
296  return *this;
297  }
298 }; // class DenseMaskIterator
299 
300 
306 template<Index Log2Dim>
307 class NodeMask
308 {
309 public:
310  BOOST_STATIC_ASSERT( Log2Dim>2 );
311 
312  static const Index32 LOG2DIM = Log2Dim;
313  static const Index32 DIM = 1<<Log2Dim;
314  static const Index32 SIZE = 1<<3*Log2Dim;
315  static const Index32 WORD_COUNT = SIZE >> 6;// 2^6=64
316  typedef Index64 Word;
317 
318 private:
319 
320  // The bits are represented as a linear array of Words, and the
321  // size of a Word is 32 or 64 bits depending on the platform.
322  // The BIT_MASK is defined as the number of bits in a Word - 1
323  //static const Index32 BIT_MASK = sizeof(void*) == 8 ? 63 : 31;
324  //static const Index32 LOG2WORD = BIT_MASK == 63 ? 6 : 5;
325  //static const Index32 WORD_COUNT = SIZE >> LOG2WORD;
326  //typedef boost::mpl::if_c<BIT_MASK == 63, Index64, Index32>::type Word;
327 
328  Word mWords[WORD_COUNT];//only member data!
329 
330 public:
332  NodeMask() { this->setOff(); }
334  NodeMask(bool on) { this->set(on); }
336  NodeMask(const NodeMask &other) { *this = other; }
340  NodeMask& operator=(const NodeMask& other)
341  {
342  Index32 n = WORD_COUNT;
343  const Word* w2 = other.mWords;
344  for (Word* w1 = mWords; n--; ++w1, ++w2) *w1 = *w2;
345  return *this;
346  }
347 
351 
352  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
353  OnIterator endOn() const { return OnIterator(SIZE,this); }
354  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
355  OffIterator endOff() const { return OffIterator(SIZE,this); }
356  DenseIterator beginDense() const { return DenseIterator(0,this); }
357  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
358 
359  bool operator == (const NodeMask &other) const
360  {
361  int n = WORD_COUNT;
362  for (const Word *w1=mWords, *w2=other.mWords; n-- && *w1++ == *w2++;) ;
363  return n == -1;
364  }
365 
366  bool operator != (const NodeMask &other) const { return !(*this == other); }
367 
368  //
369  // Bitwise logical operations
370  //
371 
378  template<typename WordOp>
379  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
380  {
381  Word *w1 = mWords;
382  const Word *w2 = other.mWords;
383  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) op( *w1, *w2);
384  return *this;
385  }
386  template<typename WordOp>
387  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
388  {
389  Word *w1 = mWords;
390  const Word *w2 = other1.mWords, *w3 = other2.mWords;
391  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3) op( *w1, *w2, *w3);
392  return *this;
393  }
394  template<typename WordOp>
395  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
396  const WordOp& op)
397  {
398  Word *w1 = mWords;
399  const Word *w2 = other1.mWords, *w3 = other2.mWords, *w4 = other3.mWords;
400  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3, ++w4) op( *w1, *w2, *w3, *w4);
401  return *this;
402  }
404  const NodeMask& operator&=(const NodeMask& other)
405  {
406  Word *w1 = mWords;
407  const Word *w2 = other.mWords;
408  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= *w2;
409  return *this;
410  }
412  const NodeMask& operator|=(const NodeMask& other)
413  {
414  Word *w1 = mWords;
415  const Word *w2 = other.mWords;
416  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 |= *w2;
417  return *this;
418  }
420  const NodeMask& operator-=(const NodeMask& other)
421  {
422  Word *w1 = mWords;
423  const Word *w2 = other.mWords;
424  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= ~*w2;
425  return *this;
426  }
428  const NodeMask& operator^=(const NodeMask& other)
429  {
430  Word *w1 = mWords;
431  const Word *w2 = other.mWords;
432  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 ^= *w2;
433  return *this;
434  }
435  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
436  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
437  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
438  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
439 
441  static Index32 memUsage() { return static_cast<Index32>(WORD_COUNT*sizeof(Word)); }
443  Index32 countOn() const
444  {
445  Index32 sum = 0, n = WORD_COUNT;
446  for (const Word* w = mWords; n--; ++w) sum += CountOn(*w);
447  return sum;
448  }
450  Index32 countOff() const { return SIZE-this->countOn(); }
452  void setOn(Index32 n) {
453  assert( (n >> 6) < WORD_COUNT );
454  mWords[n >> 6] |= Word(1) << (n & 63);
455  }
457  void setOff(Index32 n) {
458  assert( (n >> 6) < WORD_COUNT );
459  mWords[n >> 6] &= ~(Word(1) << (n & 63));
460  }
462  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
464  void set(bool on)
465  {
466  const Word state = on ? ~Word(0) : Word(0);
467  Index32 n = WORD_COUNT;
468  for (Word* w = mWords; n--; ++w) *w = state;
469  }
471  void setOn()
472  {
473  Index32 n = WORD_COUNT;
474  for (Word* w = mWords; n--; ++w) *w = ~Word(0);
475  }
477  void setOff()
478  {
479  Index32 n = WORD_COUNT;
480  for (Word* w = mWords; n--; ++w) *w = Word(0);
481  }
483  void toggle(Index32 n) {
484  assert( (n >> 6) < WORD_COUNT );
485  mWords[n >> 6] ^= Word(1) << (n & 63);
486  }
488  void toggle()
489  {
490  Index32 n = WORD_COUNT;
491  for (Word* w = mWords; n--; ++w) *w = ~*w;
492  }
494  void setFirstOn() { this->setOn(0); }
496  void setLastOn() { this->setOn(SIZE-1); }
498  void setFirstOff() { this->setOff(0); }
500  void setLastOff() { this->setOff(SIZE-1); }
502  bool isOn(Index32 n) const
503  {
504  assert( (n >> 6) < WORD_COUNT );
505  return 0 != (mWords[n >> 6] & (Word(1) << (n & 63)));
506  }
508  bool isOff(Index32 n) const {return !this->isOn(n); }
510  bool isOn() const
511  {
512  int n = WORD_COUNT;
513  for (const Word *w = mWords; n-- && *w++ == ~Word(0);) ;
514  return n == -1;
515  }
517  bool isOff() const
518  {
519  int n = WORD_COUNT;
520  for (const Word *w = mWords; n-- && *w++ == Word(0);) ;
521  return n == -1;
522  }
526  bool isConstant(bool &isOn) const
527  {
528  isOn = (mWords[0] == ~Word(0));//first word has all bits on
529  if ( !isOn && mWords[0] != Word(0)) return false;//early out
530  const Word *w = mWords + 1, *n = mWords + WORD_COUNT;
531  while( w<n && *w == mWords[0] ) ++w;
532  return w == n;
533  }
535  {
536  Index32 n = 0;
537  const Word* w = mWords;
538  for (; n<WORD_COUNT && !*w; ++w, ++n) ;
539  return n==WORD_COUNT ? SIZE : (n << 6) + FindLowestOn(*w);
540  }
542  {
543  Index32 n = 0;
544  const Word* w = mWords;
545  for (; n<WORD_COUNT && !~*w; ++w, ++n) ;
546  return n==WORD_COUNT ? SIZE : (n << 6) + FindLowestOn(~*w);
547  }
548 
550  template<typename WordT>
552  WordT getWord(Index n) const
553  {
554  assert(n*8*sizeof(WordT) < SIZE);
555  return reinterpret_cast<const WordT*>(mWords)[n];
556  }
557  template<typename WordT>
558  WordT& getWord(Index n)
559  {
560  assert(n*8*sizeof(WordT) < SIZE);
561  return reinterpret_cast<WordT*>(mWords)[n];
562  }
564 
565  void save(std::ostream& os) const
566  {
567  os.write(reinterpret_cast<const char*>(mWords), this->memUsage());
568  }
569  void load(std::istream& is) {
570  is.read(reinterpret_cast<char*>(mWords), this->memUsage());
571  }
572  void seek(std::istream& is) const {
573  is.seekg(this->memUsage(), std::ios_base::cur);
574  }
576  void printInfo(std::ostream& os=std::cout) const
577  {
578  os << "NodeMask: Dim=" << DIM << " Log2Dim=" << Log2Dim
579  << " Bit count=" << SIZE << " word count=" << WORD_COUNT << std::endl;
580  }
581  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const
582  {
583  const Index32 n=(SIZE>max_out ? max_out : SIZE);
584  for (Index32 i=0; i < n; ++i) {
585  if ( !(i & 63) )
586  os << "||";
587  else if ( !(i%8) )
588  os << "|";
589  os << this->isOn(i);
590  }
591  os << "|" << std::endl;
592  }
593  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const
594  {
595  this->printInfo(os);
596  this->printBits(os, max_out);
597  }
598 
600  {
601  Index32 n = start >> 6;//initiate
602  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
603  Index32 m = start & 63;
604  Word b = mWords[n];
605  if (b & (Word(1) << m)) return start;//simpel case: start is on
606  b &= ~Word(0) << m;// mask out lower bits
607  while(!b && ++n<WORD_COUNT) b = mWords[n];// find next none-zero word
608  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
609  }
610 
612  {
613  Index32 n = start >> 6;//initiate
614  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
615  Index32 m = start & 63;
616  Word b = ~mWords[n];
617  if (b & (Word(1) << m)) return start;//simpel case: start is on
618  b &= ~Word(0) << m;// mask out lower bits
619  while(!b && ++n<WORD_COUNT) b = ~mWords[n];// find next none-zero word
620  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
621  }
622 };// NodeMask
623 
624 
626 template<>
627 class NodeMask<1>
628 {
629 public:
630 
631  static const Index32 LOG2DIM = 1;
632  static const Index32 DIM = 2;
633  static const Index32 SIZE = 8;
634  static const Index32 WORD_COUNT = 1;
635  typedef Byte Word;
636 
637 private:
638 
639  Byte mByte;//only member data!
640 
641 public:
643  NodeMask() : mByte(0x00U) {}
645  NodeMask(bool on) : mByte(on ? 0xFFU : 0x00U) {}
647  NodeMask(const NodeMask &other) : mByte(other.mByte) {}
651  void operator = (const NodeMask &other) { mByte = other.mByte; }
652 
656 
657  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
658  OnIterator endOn() const { return OnIterator(SIZE,this); }
659  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
660  OffIterator endOff() const { return OffIterator(SIZE,this); }
661  DenseIterator beginDense() const { return DenseIterator(0,this); }
662  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
663 
664  bool operator == (const NodeMask &other) const { return mByte == other.mByte; }
665 
666  bool operator != (const NodeMask &other) const {return mByte != other.mByte; }
667 
668  //
669  // Bitwise logical operations
670  //
671 
678  template<typename WordOp>
679  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
680  {
681  op(mByte, other.mByte);
682  return *this;
683  }
684  template<typename WordOp>
685  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
686  {
687  op(mByte, other1.mByte, other2.mByte);
688  return *this;
689  }
690  template<typename WordOp>
691  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
692  const WordOp& op)
693  {
694  op(mByte, other1.mByte, other2.mByte, other3.mByte);
695  return *this;
696  }
698  const NodeMask& operator&=(const NodeMask& other)
699  {
700  mByte &= other.mByte;
701  return *this;
702  }
704  const NodeMask& operator|=(const NodeMask& other)
705  {
706  mByte |= other.mByte;
707  return *this;
708  }
710  const NodeMask& operator-=(const NodeMask& other)
711  {
712  mByte &= static_cast<Byte>(~other.mByte);
713  return *this;
714  }
716  const NodeMask& operator^=(const NodeMask& other)
717  {
718  mByte ^= other.mByte;
719  return *this;
720  }
721  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
722  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
723  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
724  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
726  static Index32 memUsage() { return 1; }
728  Index32 countOn() const { return CountOn(mByte); }
730  Index32 countOff() const { return CountOff(mByte); }
732  void setOn(Index32 n) {
733  assert( n < 8 );
734  mByte = mByte | static_cast<Byte>(0x01U << (n & 7));
735  }
737  void setOff(Index32 n) {
738  assert( n < 8 );
739  mByte = mByte & static_cast<Byte>(~(0x01U << (n & 7)));
740  }
742  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
744  void set(bool on) { mByte = on ? 0xFFU : 0x00U; }
746  void setOn() { mByte = 0xFFU; }
748  void setOff() { mByte = 0x00U; }
750  void toggle(Index32 n) {
751  assert( n < 8 );
752  mByte = mByte ^ static_cast<Byte>(0x01U << (n & 7));
753  }
755  void toggle() { mByte = static_cast<Byte>(~mByte); }
757  void setFirstOn() { this->setOn(0); }
759  void setLastOn() { this->setOn(7); }
761  void setFirstOff() { this->setOff(0); }
763  void setLastOff() { this->setOff(7); }
765  bool isOn(Index32 n) const
766  {
767  assert( n < 8 );
768  return mByte & (0x01U << (n & 7));
769  }
771  bool isOff(Index32 n) const {return !this->isOn(n); }
773  bool isOn() const { return mByte == 0xFFU; }
775  bool isOff() const { return mByte == 0; }
779  bool isConstant(bool &isOn) const
780  {
781  isOn = this->isOn();
782  return isOn || this->isOff();
783  }
784  Index32 findFirstOn() const { return mByte ? FindLowestOn(mByte) : 8; }
786  {
787  const Byte b = static_cast<Byte>(~mByte);
788  return b ? FindLowestOn(b) : 8;
789  }
790  /*
792  template<typename WordT>
795  WordT getWord(Index n) const
796  {
797  BOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
798  assert(n == 0);
799  return reinterpret_cast<WordT>(mByte);
800  }
801  template<typename WordT>
802  WordT& getWord(Index n)
803  {
804  BOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
805  assert(n == 0);
806  return reinterpret_cast<WordT&>(mByte);
807  }
809  */
810  void save(std::ostream& os) const
811  {
812  os.write(reinterpret_cast<const char*>(&mByte), 1);
813  }
814  void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mByte), 1); }
815  void seek(std::istream& is) const { is.seekg(1, std::ios_base::cur); }
817  void printInfo(std::ostream& os=std::cout) const
818  {
819  os << "NodeMask: Dim=2, Log2Dim=1, Bit count=8, Word count=1"<<std::endl;
820  }
821  void printBits(std::ostream& os=std::cout) const
822  {
823  os << "||";
824  for (Index32 i=0; i < 8; ++i) os << this->isOn(i);
825  os << "||" << std::endl;
826  }
827  void printAll(std::ostream& os=std::cout) const
828  {
829  this->printInfo(os);
830  this->printBits(os);
831  }
832 
834  {
835  if (start>=8) return 8;
836  const Byte b = static_cast<Byte>(mByte & (0xFFU << start));
837  return b ? FindLowestOn(b) : 8;
838  }
839 
841  {
842  if (start>=8) return 8;
843  const Byte b = static_cast<Byte>(~mByte & (0xFFU << start));
844  return b ? FindLowestOn(b) : 8;
845  }
846 
847 };// NodeMask<1>
848 
849 
851 template<>
852 class NodeMask<2>
853 {
854 public:
855 
856  static const Index32 LOG2DIM = 2;
857  static const Index32 DIM = 4;
858  static const Index32 SIZE = 64;
859  static const Index32 WORD_COUNT = 1;
860  typedef Index64 Word;
861 
862 private:
863 
864  Word mWord;//only member data!
865 
866 public:
868  NodeMask() : mWord(UINT64_C(0x00)) {}
870  NodeMask(bool on) : mWord(on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00)) {}
872  NodeMask(const NodeMask &other) : mWord(other.mWord) {}
876  void operator = (const NodeMask &other) { mWord = other.mWord; }
877 
881 
882  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
883  OnIterator endOn() const { return OnIterator(SIZE,this); }
884  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
885  OffIterator endOff() const { return OffIterator(SIZE,this); }
886  DenseIterator beginDense() const { return DenseIterator(0,this); }
887  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
888 
889  bool operator == (const NodeMask &other) const { return mWord == other.mWord; }
890 
891  bool operator != (const NodeMask &other) const {return mWord != other.mWord; }
892 
893  //
894  // Bitwise logical operations
895  //
896 
903  template<typename WordOp>
904  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
905  {
906  op(mWord, other.mWord);
907  return *this;
908  }
909  template<typename WordOp>
910  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
911  {
912  op(mWord, other1.mWord, other2.mWord);
913  return *this;
914  }
915  template<typename WordOp>
916  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
917  const WordOp& op)
918  {
919  op(mWord, other1.mWord, other2.mWord, other3.mWord);
920  return *this;
921  }
923  const NodeMask& operator&=(const NodeMask& other)
924  {
925  mWord &= other.mWord;
926  return *this;
927  }
929  const NodeMask& operator|=(const NodeMask& other)
930  {
931  mWord |= other.mWord;
932  return *this;
933  }
935  const NodeMask& operator-=(const NodeMask& other)
936  {
937  mWord &= ~other.mWord;
938  return *this;
939  }
941  const NodeMask& operator^=(const NodeMask& other)
942  {
943  mWord ^= other.mWord;
944  return *this;
945  }
946  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
947  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
948  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
949  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
951  static Index32 memUsage() { return 8; }
953  Index32 countOn() const { return CountOn(mWord); }
955  Index32 countOff() const { return CountOff(mWord); }
957  void setOn(Index32 n) {
958  assert( n < 64 );
959  mWord |= UINT64_C(0x01) << (n & 63);
960  }
962  void setOff(Index32 n) {
963  assert( n < 64 );
964  mWord &= ~(UINT64_C(0x01) << (n & 63));
965  }
967  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
969  void set(bool on) { mWord = on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00); }
971  void setOn() { mWord = UINT64_C(0xFFFFFFFFFFFFFFFF); }
973  void setOff() { mWord = UINT64_C(0x00); }
975  void toggle(Index32 n) {
976  assert( n < 64 );
977  mWord ^= UINT64_C(0x01) << (n & 63);
978  }
980  void toggle() { mWord = ~mWord; }
982  void setFirstOn() { this->setOn(0); }
984  void setLastOn() { this->setOn(63); }
986  void setFirstOff() { this->setOff(0); }
988  void setLastOff() { this->setOff(63); }
990  bool isOn(Index32 n) const
991  {
992  assert( n < 64 );
993  return 0 != (mWord & (UINT64_C(0x01) << (n & 63)));
994  }
996  bool isOff(Index32 n) const {return !this->isOn(n); }
998  bool isOn() const { return mWord == UINT64_C(0xFFFFFFFFFFFFFFFF); }
1000  bool isOff() const { return mWord == 0; }
1004  bool isConstant(bool &isOn) const
1005  { isOn = this->isOn();
1006  return isOn || this->isOff();
1007  }
1008  Index32 findFirstOn() const { return mWord ? FindLowestOn(mWord) : 64; }
1010  {
1011  const Word w = ~mWord;
1012  return w ? FindLowestOn(w) : 64;
1013  }
1015  template<typename WordT>
1017  WordT getWord(Index n) const
1018  {
1019  assert(n*8*sizeof(WordT) < SIZE);
1020  return reinterpret_cast<const WordT*>(&mWord)[n];
1021  }
1022  template<typename WordT>
1023  WordT& getWord(Index n)
1024  {
1025  assert(n*8*sizeof(WordT) < SIZE);
1026  return reinterpret_cast<WordT*>(mWord)[n];
1027  }
1029  void save(std::ostream& os) const
1030  {
1031  os.write(reinterpret_cast<const char*>(&mWord), 8);
1032  }
1033  void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mWord), 8); }
1034  void seek(std::istream& is) const { is.seekg(8, std::ios_base::cur); }
1036  void printInfo(std::ostream& os=std::cout) const
1037  {
1038  os << "NodeMask: Dim=4, Log2Dim=2, Bit count=64, Word count=1"<<std::endl;
1039  }
1040  void printBits(std::ostream& os=std::cout) const
1041  {
1042  os << "|";
1043  for (Index32 i=0; i < 64; ++i) {
1044  if ( !(i%8) ) os << "|";
1045  os << this->isOn(i);
1046  }
1047  os << "||" << std::endl;
1048  }
1049  void printAll(std::ostream& os=std::cout) const
1050  {
1051  this->printInfo(os);
1052  this->printBits(os);
1053  }
1054 
1056  {
1057  if (start>=64) return 64;
1058  const Word w = mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1059  return w ? FindLowestOn(w) : 64;
1060  }
1061 
1063  {
1064  if (start>=64) return 64;
1065  const Word w = ~mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1066  return w ? FindLowestOn(w) : 64;
1067  }
1068 
1069 };// NodeMask<2>
1070 
1071 
1072 // Unlike NodeMask above this RootNodeMask has a run-time defined size.
1073 // It is only included for backward compatibility and will likely be
1074 // deprecated in the future!
1075 // This class is 32-bit specefic, hence the use if Index32 vs Index!
1077 {
1078 protected:
1079  Index32 mBitSize, mIntSize;
1081 
1082 public:
1083  RootNodeMask(): mBitSize(0), mIntSize(0), mBits(nullptr) {}
1085  mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new Index32[mIntSize])
1086  {
1087  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1088  }
1090  mBitSize(B.mBitSize), mIntSize(B.mIntSize), mBits(new Index32[mIntSize])
1091  {
1092  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1093  }
1094  ~RootNodeMask() {delete [] mBits;}
1095 
1096  void init(Index32 bit_size) {
1097  mBitSize = bit_size;
1098  mIntSize =((bit_size-1)>>5)+1;
1099  delete [] mBits;
1100  mBits = new Index32[mIntSize];
1101  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1102  }
1103 
1104  Index getBitSize() const {return mBitSize;}
1105 
1106  Index getIntSize() const {return mIntSize;}
1107 
1109  if (mBitSize!=B.mBitSize) {
1110  mBitSize=B.mBitSize;
1111  mIntSize=B.mIntSize;
1112  delete [] mBits;
1113  mBits = new Index32[mIntSize];
1114  }
1115  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1116  return *this;
1117  }
1118 
1120  {
1121  protected:
1122  Index32 mPos;//bit position
1124  const RootNodeMask* mParent;//this iterator can't change the parent_mask!
1125  public:
1126  BaseIterator() : mPos(0), mBitSize(0), mParent(nullptr) {}
1127  BaseIterator(const BaseIterator&) = default;
1128  BaseIterator(Index32 pos, const RootNodeMask* parent):
1129  mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) { assert(pos <= mBitSize); }
1130  bool operator==(const BaseIterator &iter) const {return mPos == iter.mPos;}
1131  bool operator!=(const BaseIterator &iter) const {return mPos != iter.mPos;}
1132  bool operator< (const BaseIterator &iter) const {return mPos < iter.mPos;}
1134  mPos = iter.mPos;
1135  mBitSize = iter.mBitSize;
1136  mParent = iter.mParent;
1137  return *this;
1138  }
1139 
1140  Index32 offset() const {return mPos;}
1141 
1142  Index32 pos() const {return mPos;}
1143 
1144  bool test() const {
1145  assert(mPos <= mBitSize);
1146  return (mPos != mBitSize);
1147  }
1148 
1149  operator bool() const {return this->test();}
1150  }; // class BaseIterator
1151 
1153  class OnIterator: public BaseIterator
1154  {
1155  protected:
1156  using BaseIterator::mPos;//bit position;
1157  using BaseIterator::mBitSize;//bit size;
1158  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1159  public:
1161  OnIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1162  void increment() {
1163  assert(mParent != nullptr);
1164  mPos=mParent->findNextOn(mPos+1);
1165  assert(mPos <= mBitSize);
1166  }
1167  void increment(Index n) {
1168  for (Index i=0; i<n && this->next(); ++i) {}
1169  }
1170  bool next() {
1171  this->increment();
1172  return this->test();
1173  }
1174  bool operator*() const {return true;}
1175  OnIterator& operator++() {
1176  this->increment();
1177  return *this;
1178  }
1179  }; // class OnIterator
1180 
1181  class OffIterator: public BaseIterator
1182  {
1183  protected:
1184  using BaseIterator::mPos;//bit position;
1185  using BaseIterator::mBitSize;//bit size;
1186  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1187  public:
1189  OffIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1190  void increment() {
1191  assert(mParent != nullptr);
1192  mPos=mParent->findNextOff(mPos+1);
1193  assert(mPos <= mBitSize);
1194  }
1195  void increment(Index n) {
1196  for (Index i=0; i<n && this->next(); ++i) {}
1197  }
1198  bool next() {
1199  this->increment();
1200  return this->test();
1201  }
1202  bool operator*() const {return true;}
1203  OffIterator& operator++() {
1204  this->increment();
1205  return *this;
1206  }
1207  }; // class OffIterator
1208 
1209  class DenseIterator: public BaseIterator
1210  {
1211  protected:
1212  using BaseIterator::mPos;//bit position;
1213  using BaseIterator::mBitSize;//bit size;
1214  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1215  public:
1217  DenseIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1218  void increment() {
1219  assert(mParent != nullptr);
1220  mPos += 1;//carefull - the increament might go beyond the end
1221  assert(mPos<= mBitSize);
1222  }
1223  void increment(Index n) {
1224  for (Index i=0; i<n && this->next(); ++i) {}
1225  }
1226  bool next() {
1227  this->increment();
1228  return this->test();
1229  }
1230  bool operator*() const {return mParent->isOn(mPos);}
1231  DenseIterator& operator++() {
1232  this->increment();
1233  return *this;
1234  }
1235  }; // class DenseIterator
1236 
1237  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
1238  OnIterator endOn() const { return OnIterator(mBitSize,this); }
1239  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
1240  OffIterator endOff() const { return OffIterator(mBitSize,this); }
1241  DenseIterator beginDense() const { return DenseIterator(0,this); }
1242  DenseIterator endDense() const { return DenseIterator(mBitSize,this); }
1243 
1244  bool operator == (const RootNodeMask &B) const {
1245  if (mBitSize != B.mBitSize) return false;
1246  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return false;
1247  return true;
1248  }
1249 
1250  bool operator != (const RootNodeMask &B) const {
1251  if (mBitSize != B.mBitSize) return true;
1252  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return true;
1253  return false;
1254  }
1255 
1256  //
1257  // Bitwise logical operations
1258  //
1259  RootNodeMask operator!() const { RootNodeMask m = *this; m.toggle(); return m; }
1260  const RootNodeMask& operator&=(const RootNodeMask& other) {
1261  assert(mIntSize == other.mIntSize);
1262  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1263  mBits[i] &= other.mBits[i];
1264  }
1265  for (Index32 i = other.mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
1266  return *this;
1267  }
1268  const RootNodeMask& operator|=(const RootNodeMask& other) {
1269  assert(mIntSize == other.mIntSize);
1270  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1271  mBits[i] |= other.mBits[i];
1272  }
1273  return *this;
1274  }
1275  const RootNodeMask& operator^=(const RootNodeMask& other) {
1276  assert(mIntSize == other.mIntSize);
1277  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1278  mBits[i] ^= other.mBits[i];
1279  }
1280  return *this;
1281  }
1282  RootNodeMask operator&(const RootNodeMask& other) const {
1283  RootNodeMask m(*this); m &= other; return m;
1284  }
1285  RootNodeMask operator|(const RootNodeMask& other) const {
1286  RootNodeMask m(*this); m |= other; return m;
1287  }
1288  RootNodeMask operator^(const RootNodeMask& other) const {
1289  RootNodeMask m(*this); m ^= other; return m;
1290  }
1291 
1292 
1294  return static_cast<Index32>(mIntSize*sizeof(Index32) + sizeof(*this));
1295  }
1296 
1297  Index32 countOn() const {
1298  assert(mBits);
1299  Index32 n=0;
1300  for (Index32 i=0; i< mIntSize; ++i) n += CountOn(mBits[i]);
1301  return n;
1302  }
1303 
1304  Index32 countOff() const { return mBitSize-this->countOn(); }
1305 
1306  void setOn(Index32 i) {
1307  assert(mBits);
1308  assert( (i>>5) < mIntSize);
1309  mBits[i>>5] |= 1<<(i&31);
1310  }
1311 
1312  void setOff(Index32 i) {
1313  assert(mBits);
1314  assert( (i>>5) < mIntSize);
1315  mBits[i>>5] &= ~(1<<(i&31));
1316  }
1317 
1318  void set(Index32 i, bool On) { On ? this->setOn(i) : this->setOff(i); }
1319 
1320  void setOn() {
1321  assert(mBits);
1322  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
1323  }
1324  void setOff() {
1325  assert(mBits);
1326  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1327  }
1328  void toggle(Index32 i) {
1329  assert(mBits);
1330  assert( (i>>5) < mIntSize);
1331  mBits[i>>5] ^= 1<<(i&31);
1332  }
1333  void toggle() {
1334  assert(mBits);
1335  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
1336  }
1337  void setFirstOn() { this->setOn(0); }
1338  void setLastOn() { this->setOn(mBitSize-1); }
1339  void setFirstOff() { this->setOff(0); }
1340  void setLastOff() { this->setOff(mBitSize-1); }
1341  bool isOn(Index32 i) const {
1342  assert(mBits);
1343  assert( (i>>5) < mIntSize);
1344  return ( mBits[i >> 5] & (1<<(i&31)) );
1345  }
1346  bool isOff(Index32 i) const {
1347  assert(mBits);
1348  assert( (i>>5) < mIntSize);
1349  return ( ~mBits[i >> 5] & (1<<(i&31)) );
1350  }
1351 
1352  bool isOn() const {
1353  if (!mBits) return false;//undefined is off
1354  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0xFFFFFFFF) return false;
1355  return true;
1356  }
1357 
1358  bool isOff() const {
1359  if (!mBits) return true;//undefined is off
1360  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0) return false;
1361  return true;
1362  }
1363 
1365  assert(mBits);
1366  Index32 i=0;
1367  while(!mBits[i]) if (++i == mIntSize) return mBitSize;//reached end
1368  return 32*i + FindLowestOn(mBits[i]);
1369  }
1370 
1372  assert(mBits);
1373  Index32 i=0;
1374  while(!(~mBits[i])) if (++i == mIntSize) return mBitSize;//reached end
1375  return 32*i + FindLowestOn(~mBits[i]);
1376  }
1377 
1378  void save(std::ostream& os) const {
1379  assert(mBits);
1380  os.write(reinterpret_cast<const char*>(mBits), mIntSize * sizeof(Index32));
1381  }
1382  void load(std::istream& is) {
1383  assert(mBits);
1384  is.read(reinterpret_cast<char*>(mBits), mIntSize * sizeof(Index32));
1385  }
1386  void seek(std::istream& is) const {
1387  assert(mBits);
1388  is.seekg(mIntSize * sizeof(Index32), std::ios_base::cur);
1389  }
1391  void printInfo(std::ostream& os=std::cout) const {
1392  os << "RootNodeMask: Bit-size="<<mBitSize<<" Int-size="<<mIntSize<<std::endl;
1393  }
1394 
1395  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const {
1396  const Index32 n=(mBitSize>max_out?max_out:mBitSize);
1397  for (Index32 i=0; i < n; ++i) {
1398  if ( !(i&31) )
1399  os << "||";
1400  else if ( !(i%8) )
1401  os << "|";
1402  os << this->isOn(i);
1403  }
1404  os << "|" << std::endl;
1405  }
1406 
1407  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const {
1408  this->printInfo(os);
1409  this->printBits(os,max_out);
1410  }
1411 
1412  Index32 findNextOn(Index32 start) const {
1413  assert(mBits);
1414  Index32 n = start >> 5, m = start & 31;//initiate
1415  if (n>=mIntSize) return mBitSize; // check for out of bounds
1416  Index32 b = mBits[n];
1417  if (b & (1<<m)) return start;//simple case
1418  b &= 0xFFFFFFFF << m;// mask lower bits
1419  while(!b && ++n<mIntSize) b = mBits[n];// find next nonzero int
1420  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1421  }
1422 
1423  Index32 findNextOff(Index32 start) const {
1424  assert(mBits);
1425  Index32 n = start >> 5, m = start & 31;//initiate
1426  if (n>=mIntSize) return mBitSize; // check for out of bounds
1427  Index32 b = ~mBits[n];
1428  if (b & (1<<m)) return start;//simple case
1429  b &= 0xFFFFFFFF<<m;// mask lower bits
1430  while(!b && ++n<mIntSize) b = ~mBits[n];// find next nonzero int
1431  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1432  }
1433 
1434  Index32 memUsage() const {
1435  assert(mBits);
1436  return static_cast<Index32>(sizeof(Index32*)+(2+mIntSize)*sizeof(Index32));//in bytes
1437  }
1438 }; // class RootNodeMask
1439 
1440 } // namespace util
1441 } // namespace OPENVDB_VERSION_NAME
1442 } // namespace openvdb
1443 
1444 #endif // OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
1445 
1446 // Copyright (c) 2012-2017 DreamWorks Animation LLC
1447 // All rights reserved. This software is distributed under the
1448 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:757
OnIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1161
bool isOn() const
Definition: NodeMasks.h:1352
DenseIterator beginDense() const
Definition: NodeMasks.h:1241
bool test() const
Definition: NodeMasks.h:201
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:975
void save(std::ostream &os) const
Definition: NodeMasks.h:1378
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:348
void setLastOn()
Definition: NodeMasks.h:1338
void increment()
Definition: NodeMasks.h:1190
void increment()
Definition: NodeMasks.h:280
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:750
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:827
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1036
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:611
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:704
OnMaskIterator()
Definition: NodeMasks.h:215
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1049
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:779
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition: Vec3.h:495
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:1004
DenseMaskIterator()
Definition: NodeMasks.h:278
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:948
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:156
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:552
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:710
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:775
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:996
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:502
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:935
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:929
Index32 CountOn(Index64 v)
Return the number of on bits in the given 64-bit value.
Definition: NodeMasks.h:97
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1423
void increment()
Definition: NodeMasks.h:1162
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:771
bool operator!=(const BaseIterator &iter) const
Definition: NodeMasks.h:1131
RootNodeMask(const RootNodeMask &B)
Definition: NodeMasks.h:1089
NodeMask & operator=(const NodeMask &other)
Assignment operator.
Definition: NodeMasks.h:340
uint32_t Index32
Definition: Types.h:55
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:510
DenseIterator & operator++()
Definition: NodeMasks.h:1231
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:723
void increment()
Definition: NodeMasks.h:248
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:1000
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1412
Index32 mIntSize
Definition: NodeMasks.h:1079
bool next()
Definition: NodeMasks.h:1198
Definition: NodeMasks.h:1076
tbb::atomic< Index32 > i
Definition: LeafBuffer.h:71
Index32 findFirstOn() const
Definition: NodeMasks.h:534
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1017
Index32 mBitSize
Definition: NodeMasks.h:1123
Index32 findFirstOn() const
Definition: NodeMasks.h:784
OnMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:216
Index32 CountOff(Index64 v)
Return the number of off bits in the given 64-bit value.
Definition: NodeMasks.h:106
void toggle()
Definition: NodeMasks.h:1333
void save(std::ostream &os) const
Definition: NodeMasks.h:1029
Index32 findFirstOn() const
Definition: NodeMasks.h:1008
const RootNodeMask * mParent
Definition: NodeMasks.h:1124
Index32 * mBits
Definition: NodeMasks.h:1080
Index32 pos() const
Definition: NodeMasks.h:200
OffIterator beginOff() const
Definition: NodeMasks.h:354
bool operator*() const
Definition: NodeMasks.h:1174
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:761
RootNodeMask & operator=(const RootNodeMask &B)
Definition: NodeMasks.h:1108
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:821
void setOff()
Set all bits off.
Definition: NodeMasks.h:477
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:728
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:990
Index32 Index
Definition: Types.h:57
bool test() const
Definition: NodeMasks.h:1144
Definition: NodeMasks.h:270
Index32 mPos
Definition: NodeMasks.h:1122
void increment(Index n)
Definition: NodeMasks.h:223
NodeMask operator!() const
Definition: NodeMasks.h:721
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:953
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1391
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:765
void save(std::ostream &os) const
Definition: NodeMasks.h:810
Index32 memUsage() const
Definition: NodeMasks.h:1434
bool operator==(const BaseIterator &iter) const
Definition: NodeMasks.h:1130
Index32 countOn() const
Definition: NodeMasks.h:1297
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:494
NodeMask operator!() const
Definition: NodeMasks.h:946
OffIterator endOff() const
Definition: NodeMasks.h:355
DenseIterator endDense() const
Definition: NodeMasks.h:357
OnIterator beginOn() const
Definition: NodeMasks.h:1237
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:724
DenseIterator beginDense() const
Definition: NodeMasks.h:886
bool isOff() const
Definition: NodeMasks.h:1358
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:986
OffIterator endOff() const
Definition: NodeMasks.h:1240
OffIterator beginOff() const
Definition: NodeMasks.h:1239
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:428
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1040
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:980
void setOff()
Set all bits off.
Definition: NodeMasks.h:748
OffMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:247
OnIterator endOn() const
Definition: NodeMasks.h:1238
Index32 mPos
Definition: NodeMasks.h:182
const RootNodeMask & operator^=(const RootNodeMask &other)
Definition: NodeMasks.h:1275
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
Index getBitSize() const
Definition: NodeMasks.h:1104
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:755
BaseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:188
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:654
~NodeMask()
Destructor.
Definition: NodeMasks.h:649
OnIterator()
Definition: NodeMasks.h:1160
uint64_t Index64
Definition: Types.h:56
Index32 getMemUsage() const
Definition: NodeMasks.h:1293
void seek(std::istream &is) const
Definition: NodeMasks.h:1386
void setOn(Index32 i)
Definition: NodeMasks.h:1306
RootNodeMask operator^(const RootNodeMask &other) const
Definition: NodeMasks.h:1288
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:949
OnIterator endOn() const
Definition: NodeMasks.h:658
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:879
DenseIterator beginDense() const
Definition: NodeMasks.h:661
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:599
void setOff()
Set all bits off.
Definition: NodeMasks.h:973
OnIterator endOn() const
Definition: NodeMasks.h:883
#define OPENVDB_VERSION_NAME
Definition: version.h:43
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:483
OffIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1189
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:558
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:336
Index32 offset() const
Definition: NodeMasks.h:199
Index32 pos() const
Definition: NodeMasks.h:1142
~NodeMask()
Destructor.
Definition: NodeMasks.h:874
OffIterator beginOff() const
Definition: NodeMasks.h:884
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:437
BaseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1128
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:655
bool operator*() const
Definition: NodeMasks.h:292
DenseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:279
Index32 findFirstOff() const
Definition: NodeMasks.h:1009
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:726
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:332
void setOff(Index32 i)
Definition: NodeMasks.h:1312
bool next()
Definition: NodeMasks.h:1170
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:880
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1055
void toggle(Index32 i)
Definition: NodeMasks.h:1328
Index getIntSize() const
Definition: NodeMasks.h:1106
void setFirstOn()
Definition: NodeMasks.h:1337
void increment(Index n)
Definition: NodeMasks.h:1167
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:737
DenseIterator endDense() const
Definition: NodeMasks.h:1242
void seek(std::istream &is) const
Definition: NodeMasks.h:572
bool operator<(const Tuple< SIZE, T0 > &t0, const Tuple< SIZE, T1 > &t1)
Definition: Tuple.h:206
DenseMaskIterator & operator++()
Definition: NodeMasks.h:293
Base class for the bit mask iterators.
Definition: NodeMasks.h:179
Index32 findFirstOn() const
Definition: NodeMasks.h:1364
void increment(Index n)
Definition: NodeMasks.h:1195
BaseIterator()
Definition: NodeMasks.h:1126
void save(std::ostream &os) const
Definition: NodeMasks.h:565
OffIterator beginOff() const
Definition: NodeMasks.h:659
Definition: Exceptions.h:39
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:941
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:487
DenseIterator beginDense() const
Definition: NodeMasks.h:356
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:951
Index32 findFirstOff() const
Definition: NodeMasks.h:785
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:593
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:443
Index32 FindLowestOn(Index64 v)
Return the least significant on bit of the given 64-bit value.
Definition: NodeMasks.h:138
Definition: NodeMasks.h:239
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:868
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:716
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:998
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:833
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1062
bool isOn(Index32 i) const
Definition: NodeMasks.h:1341
OffIterator endOff() const
Definition: NodeMasks.h:660
BaseMaskIterator & operator=(const BaseMaskIterator &iter)
Definition: NodeMasks.h:195
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:962
void increment(Index n)
Definition: NodeMasks.h:286
void init(Index32 bit_size)
Definition: NodeMasks.h:1096
Index32 findFirstOff() const
Definition: NodeMasks.h:1371
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:984
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:872
bool isOff(Index32 i) const
Definition: NodeMasks.h:1346
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:438
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:643
~NodeMask()
Destructor.
Definition: NodeMasks.h:338
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:773
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:840
OffIterator endOff() const
Definition: NodeMasks.h:885
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:647
RootNodeMask operator|(const RootNodeMask &other) const
Definition: NodeMasks.h:1285
bool operator*() const
Definition: NodeMasks.h:1230
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:349
bool operator!=(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:193
RootNodeMask()
Definition: NodeMasks.h:1083
bool next()
Definition: NodeMasks.h:1226
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:450
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:500
OnIterator & operator++()
Definition: NodeMasks.h:1175
NodeMask operator!() const
Definition: NodeMasks.h:435
Index32 mBitSize
Definition: NodeMasks.h:1079
OffMaskIterator()
Definition: NodeMasks.h:246
BaseMaskIterator()
Definition: NodeMasks.h:186
bool next()
Definition: NodeMasks.h:255
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:759
Definition: NodeMasks.h:208
void load(std::istream &is)
Definition: NodeMasks.h:1382
RootNodeMask(Index32 bit_size)
Definition: NodeMasks.h:1084
void load(std::istream &is)
Definition: NodeMasks.h:814
void setOn()
Set all bits on.
Definition: NodeMasks.h:971
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:412
Index64 Word
Definition: NodeMasks.h:316
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:526
Byte Word
Definition: NodeMasks.h:635
void seek(std::istream &is) const
Definition: NodeMasks.h:815
OnIterator beginOn() const
Definition: NodeMasks.h:882
void setOn()
Set all bits on.
Definition: NodeMasks.h:746
bool operator*() const
Definition: NodeMasks.h:1202
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:581
void setOn()
Definition: NodeMasks.h:1320
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1407
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1023
void setFirstOff()
Definition: NodeMasks.h:1339
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:496
void increment(Index n)
Definition: NodeMasks.h:254
Index32 countOff() const
Definition: NodeMasks.h:1304
void increment(Index n)
Definition: NodeMasks.h:1223
bool operator==(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:192
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:441
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:420
void load(std::istream &is)
Definition: NodeMasks.h:1033
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:307
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:730
const NodeMask * mParent
Definition: NodeMasks.h:183
bool next()
Definition: NodeMasks.h:224
bool next()
Definition: NodeMasks.h:287
void seek(std::istream &is) const
Definition: NodeMasks.h:1034
OnIterator beginOn() const
Definition: NodeMasks.h:657
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:350
DenseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1217
DenseIterator endDense() const
Definition: NodeMasks.h:662
void setOff()
Definition: NodeMasks.h:1324
OnMaskIterator & operator++()
Definition: NodeMasks.h:230
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
BaseIterator & operator=(const BaseIterator &iter)
Definition: NodeMasks.h:1133
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:498
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1395
RootNodeMask operator!() const
Definition: NodeMasks.h:1259
OffIterator()
Definition: NodeMasks.h:1188
void load(std::istream &is)
Definition: NodeMasks.h:569
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:517
OnIterator endOn() const
Definition: NodeMasks.h:353
bool operator*() const
Definition: NodeMasks.h:229
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:508
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:763
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:653
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:576
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:957
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:955
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:334
void setLastOff()
Definition: NodeMasks.h:1340
bool operator*() const
Definition: NodeMasks.h:260
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:988
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:878
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:645
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:732
DenseIterator endDense() const
Definition: NodeMasks.h:887
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:457
void increment()
Definition: NodeMasks.h:217
void increment()
Definition: NodeMasks.h:1218
const RootNodeMask & operator|=(const RootNodeMask &other)
Definition: NodeMasks.h:1268
~RootNodeMask()
Definition: NodeMasks.h:1094
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:452
unsigned char Byte
Definition: Types.h:62
void setOn()
Set all bits on.
Definition: NodeMasks.h:471
OffMaskIterator & operator++()
Definition: NodeMasks.h:261
Index64 Word
Definition: NodeMasks.h:860
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:870
Index32 findFirstOff() const
Definition: NodeMasks.h:541
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:817
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:982
#define COUNTONB6(n)
OnIterator beginOn() const
Definition: NodeMasks.h:352
OffIterator & operator++()
Definition: NodeMasks.h:1203
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:488
Index32 offset() const
Definition: NodeMasks.h:1140