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