HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NodeMasks.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2018 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @author Ken Museth
32 ///
33 /// @file NodeMasks.h
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 <hboost/mpl/if.hpp>
45 //#include <strings.h> // for ffs
46 
47 
48 namespace openvdb {
50 namespace OPENVDB_VERSION_NAME {
51 namespace util {
52 
53 /// Return the number of on bits in the given 8-bit value.
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  /// @todo Move this table and others into, say, Util.cc
62  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 
82 /// Return the number of off bits in the given 8-bit value.
83 inline Index32 CountOff(Byte v) { return CountOn(static_cast<Byte>(~v)); }
84 
85 /// Return the number of on bits in the given 32-bit value.
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 
94 /// Return the number of off bits in the given 32-bit value.
95 inline Index32 CountOff(Index32 v) { return CountOn(~v); }
96 
97 /// Return the number of on bits in the given 64-bit value.
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 
107 /// Return the number of off bits in the given 64-bit value.
108 inline Index32 CountOff(Index64 v) { return CountOn(~v); }
109 
110 /// Return the least significant on bit of the given 8-bit value.
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 
122 /// Return the least significant on bit of the given 32-bit value.
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 
138 /// Return the least significant on bit of the given 64-bit value.
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 
156 /// Return the most significant on bit of the given 32-bit value.
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 
176 ////////////////////////////////////////
177 
178 
179 /// Base class for the bit mask iterators
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:
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 
208 /// @note This happens to be a const-iterator!
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);
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 
303 /// @brief Bit mask for the internal and leaf nodes of VDB. This
304 /// is a 64-bit implementation.
305 ///
306 /// @note A template specialization for Log2Dim=1 and Log2Dim=2 are
307 /// given below.
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 = hboost::mpl::if_c<BIT_MASK == 63, Index64, Index32>::type;
329 
330  Word mWords[WORD_COUNT];//only member data!
331 
332 public:
333  /// Default constructor sets all bits off
334  NodeMask() { this->setOff(); }
335  /// All bits are set to the specified state
336  NodeMask(bool on) { this->set(on); }
337  /// Copy constructor
338  NodeMask(const NodeMask &other) { *this = other; }
339  /// Destructor
341  /// Assignment operator
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 
374  /// @brief Apply a functor to the words of the this and the other mask.
375  ///
376  /// @details An example that implements the "operator&=" method:
377  /// @code
378  /// struct Op { inline void operator()(W &w1, const W& w2) const { w1 &= w2; } };
379  /// @endcode
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  }
405  /// @brief Bitwise intersection
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  }
413  /// @brief Bitwise union
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  }
421  /// @brief Bitwise difference
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  }
429  /// @brief Bitwise XOR
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 
442  /// Return the byte size of this NodeMask
443  static Index32 memUsage() { return static_cast<Index32>(WORD_COUNT*sizeof(Word)); }
444  /// Return the total number of on bits
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  }
451  /// Return the total number of on bits
452  Index32 countOff() const { return SIZE-this->countOn(); }
453  /// Set the <i>n</i>th bit on
454  void setOn(Index32 n) {
455  assert( (n >> 6) < WORD_COUNT );
456  mWords[n >> 6] |= Word(1) << (n & 63);
457  }
458  /// Set the <i>n</i>th bit off
459  void setOff(Index32 n) {
460  assert( (n >> 6) < WORD_COUNT );
461  mWords[n >> 6] &= ~(Word(1) << (n & 63));
462  }
463  /// Set the <i>n</i>th bit to the specified state
464  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
465  /// Set all bits to the specified state
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  }
472  /// Set all bits on
473  void setOn()
474  {
475  Index32 n = WORD_COUNT;
476  for (Word* w = mWords; n--; ++w) *w = ~Word(0);
477  }
478  /// Set all bits off
479  void setOff()
480  {
481  Index32 n = WORD_COUNT;
482  for (Word* w = mWords; n--; ++w) *w = Word(0);
483  }
484  /// Toggle the state of the <i>n</i>th bit
485  void toggle(Index32 n) {
486  assert( (n >> 6) < WORD_COUNT );
487  mWords[n >> 6] ^= Word(1) << (n & 63);
488  }
489  /// Toggle the state of all bits in the mask
490  void toggle()
491  {
492  Index32 n = WORD_COUNT;
493  for (Word* w = mWords; n--; ++w) *w = ~*w;
494  }
495  /// Set the first bit on
496  void setFirstOn() { this->setOn(0); }
497  /// Set the last bit on
498  void setLastOn() { this->setOn(SIZE-1); }
499  /// Set the first bit off
500  void setFirstOff() { this->setOff(0); }
501  /// Set the last bit off
502  void setLastOff() { this->setOff(SIZE-1); }
503  /// Return @c true if the <i>n</i>th bit is on
504  bool isOn(Index32 n) const
505  {
506  assert( (n >> 6) < WORD_COUNT );
507  return 0 != (mWords[n >> 6] & (Word(1) << (n & 63)));
508  }
509  /// Return @c true if the <i>n</i>th bit is off
510  bool isOff(Index32 n) const {return !this->isOn(n); }
511  /// Return @c true if all the bits are on
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  }
518  /// Return @c true if all the bits are off
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  }
525  /// Return @c true if bits are either all off OR all on.
526  /// @param isOn Takes on the values of all bits if the method
527  /// returns true - else it is undefined.
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 
551  //@{
552  /// Return the <i>n</i>th word of the bit mask, for a word of arbitrary size.
553  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  }
565  //@}
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); }
573  /// @brief simple print method for debugging
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 
623 /// @brief Template specialization of NodeMask for Log2Dim=1, i.e. 2^3 nodes
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:
640  /// Default constructor sets all bits off
641  NodeMask() : mByte(0x00U) {}
642  /// All bits are set to the specified state
643  NodeMask(bool on) : mByte(on ? 0xFFU : 0x00U) {}
644  /// Copy constructor
645  NodeMask(const NodeMask &other) : mByte(other.mByte) {}
646  /// Destructor
648  /// Assignment operator
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 
670  /// @brief Apply a functor to the words of the this and the other mask.
671  ///
672  /// @details An example that implements the "operator&=" method:
673  /// @code
674  /// struct Op { inline void operator()(Word &w1, const Word& w2) const { w1 &= w2; } };
675  /// @endcode
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  }
695  /// @brief Bitwise intersection
696  const NodeMask& operator&=(const NodeMask& other)
697  {
698  mByte &= other.mByte;
699  return *this;
700  }
701  /// @brief Bitwise union
702  const NodeMask& operator|=(const NodeMask& other)
703  {
704  mByte |= other.mByte;
705  return *this;
706  }
707  /// @brief Bitwise difference
708  const NodeMask& operator-=(const NodeMask& other)
709  {
710  mByte &= static_cast<Byte>(~other.mByte);
711  return *this;
712  }
713  /// @brief Bitwise XOR
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; }
723  /// Return the byte size of this NodeMask
724  static Index32 memUsage() { return 1; }
725  /// Return the total number of on bits
726  Index32 countOn() const { return CountOn(mByte); }
727  /// Return the total number of on bits
728  Index32 countOff() const { return CountOff(mByte); }
729  /// Set the <i>n</i>th bit on
730  void setOn(Index32 n) {
731  assert( n < 8 );
732  mByte = mByte | static_cast<Byte>(0x01U << (n & 7));
733  }
734  /// Set the <i>n</i>th bit off
735  void setOff(Index32 n) {
736  assert( n < 8 );
737  mByte = mByte & static_cast<Byte>(~(0x01U << (n & 7)));
738  }
739  /// Set the <i>n</i>th bit to the specified state
740  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
741  /// Set all bits to the specified state
742  void set(bool on) { mByte = on ? 0xFFU : 0x00U; }
743  /// Set all bits on
744  void setOn() { mByte = 0xFFU; }
745  /// Set all bits off
746  void setOff() { mByte = 0x00U; }
747  /// Toggle the state of the <i>n</i>th bit
748  void toggle(Index32 n) {
749  assert( n < 8 );
750  mByte = mByte ^ static_cast<Byte>(0x01U << (n & 7));
751  }
752  /// Toggle the state of all bits in the mask
753  void toggle() { mByte = static_cast<Byte>(~mByte); }
754  /// Set the first bit on
755  void setFirstOn() { this->setOn(0); }
756  /// Set the last bit on
757  void setLastOn() { this->setOn(7); }
758  /// Set the first bit off
759  void setFirstOff() { this->setOff(0); }
760  /// Set the last bit off
761  void setLastOff() { this->setOff(7); }
762  /// Return true if the <i>n</i>th bit is on
763  bool isOn(Index32 n) const
764  {
765  assert( n < 8 );
766  return mByte & (0x01U << (n & 7));
767  }
768  /// Return true if the <i>n</i>th bit is off
769  bool isOff(Index32 n) const {return !this->isOn(n); }
770  /// Return true if all the bits are on
771  bool isOn() const { return mByte == 0xFFU; }
772  /// Return true if all the bits are off
773  bool isOff() const { return mByte == 0; }
774  /// Return @c true if bits are either all off OR all on.
775  /// @param isOn Takes on the values of all bits if the method
776  /// returns true - else it is undefined.
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  /*
789  //@{
790  /// Return the <i>n</i>th word of the bit mask, for a word of arbitrary size.
791  /// @note This version assumes WordT=Byte and n=0!
792  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  }
806  //@}
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); }
811  /// @brief simple print method for debugging
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 
845 /// @brief Template specialization of NodeMask for Log2Dim=2, i.e. 4^3 nodes
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:
862  /// Default constructor sets all bits off
863  NodeMask() : mWord(UINT64_C(0x00)) {}
864  /// All bits are set to the specified state
865  NodeMask(bool on) : mWord(on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00)) {}
866  /// Copy constructor
867  NodeMask(const NodeMask &other) : mWord(other.mWord) {}
868  /// Destructor
870  /// Assignment operator
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 
892  /// @brief Apply a functor to the words of the this and the other mask.
893  ///
894  /// @details An example that implements the "operator&=" method:
895  /// @code
896  /// struct Op { inline void operator()(Word &w1, const Word& w2) const { w1 &= w2; } };
897  /// @endcode
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  }
917  /// @brief Bitwise intersection
918  const NodeMask& operator&=(const NodeMask& other)
919  {
920  mWord &= other.mWord;
921  return *this;
922  }
923  /// @brief Bitwise union
924  const NodeMask& operator|=(const NodeMask& other)
925  {
926  mWord |= other.mWord;
927  return *this;
928  }
929  /// @brief Bitwise difference
930  const NodeMask& operator-=(const NodeMask& other)
931  {
932  mWord &= ~other.mWord;
933  return *this;
934  }
935  /// @brief Bitwise XOR
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; }
945  /// Return the byte size of this NodeMask
946  static Index32 memUsage() { return 8; }
947  /// Return the total number of on bits
948  Index32 countOn() const { return CountOn(mWord); }
949  /// Return the total number of on bits
950  Index32 countOff() const { return CountOff(mWord); }
951  /// Set the <i>n</i>th bit on
952  void setOn(Index32 n) {
953  assert( n < 64 );
954  mWord |= UINT64_C(0x01) << (n & 63);
955  }
956  /// Set the <i>n</i>th bit off
957  void setOff(Index32 n) {
958  assert( n < 64 );
959  mWord &= ~(UINT64_C(0x01) << (n & 63));
960  }
961  /// Set the <i>n</i>th bit to the specified state
962  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
963  /// Set all bits to the specified state
964  void set(bool on) { mWord = on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00); }
965  /// Set all bits on
966  void setOn() { mWord = UINT64_C(0xFFFFFFFFFFFFFFFF); }
967  /// Set all bits off
968  void setOff() { mWord = UINT64_C(0x00); }
969  /// Toggle the state of the <i>n</i>th bit
970  void toggle(Index32 n) {
971  assert( n < 64 );
972  mWord ^= UINT64_C(0x01) << (n & 63);
973  }
974  /// Toggle the state of all bits in the mask
975  void toggle() { mWord = ~mWord; }
976  /// Set the first bit on
977  void setFirstOn() { this->setOn(0); }
978  /// Set the last bit on
979  void setLastOn() { this->setOn(63); }
980  /// Set the first bit off
981  void setFirstOff() { this->setOff(0); }
982  /// Set the last bit off
983  void setLastOff() { this->setOff(63); }
984  /// Return true if the <i>n</i>th bit is on
985  bool isOn(Index32 n) const
986  {
987  assert( n < 64 );
988  return 0 != (mWord & (UINT64_C(0x01) << (n & 63)));
989  }
990  /// Return true if the <i>n</i>th bit is off
991  bool isOff(Index32 n) const {return !this->isOn(n); }
992  /// Return true if all the bits are on
993  bool isOn() const { return mWord == UINT64_C(0xFFFFFFFFFFFFFFFF); }
994  /// Return true if all the bits are off
995  bool isOff() const { return mWord == 0; }
996  /// Return @c true if bits are either all off OR all on.
997  /// @param isOn Takes on the values of all bits if the method
998  /// returns true - else it is undefined.
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  }
1009  //@{
1010  /// Return the <i>n</i>th word of the bit mask, for a word of arbitrary size.
1011  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  }
1023  //@}
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); }
1027  /// @brief simple print method for debugging
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:
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  }
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;
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 
1144  /// @note This happens to be a const-iterator!
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);
1157  assert(mPos <= mBitSize);
1158  }
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);
1185  assert(mPos <= mBitSize);
1186  }
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  }
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  }
1382  /// @brief simple print method for debugging
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 
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 
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) 2012-2018 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/ )
bool operator==(const RootNodeMask &B) const
Definition: NodeMasks.h:1236
RootNodeMask operator^(const RootNodeMask &other) const
Definition: NodeMasks.h:1280
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:498
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1054
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:740
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:422
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1404
Index32 CountOff(Byte v)
Return the number of off bits in the given 8-bit value.
Definition: NodeMasks.h:83
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:445
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:991
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:597
bool operator==(const NodeMask &other) const
Definition: NodeMasks.h:361
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:918
OnMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:218
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1415
const GLdouble * v
Definition: glcorearb.h:836
GLuint start
Definition: glcorearb.h:474
void seek(std::istream &is) const
Definition: NodeMasks.h:572
#define COUNTONB6(n)
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:459
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:439
BaseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:190
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:443
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:970
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:702
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:773
RootNodeMask operator&(const RootNodeMask &other) const
Definition: NodeMasks.h:1274
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:962
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1018
const RootNodeMask & operator^=(const RootNodeMask &other)
Definition: NodeMasks.h:1267
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:189
bool operator<(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:196
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1041
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:643
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:485
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:863
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:930
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:985
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:579
png_uint_32 i
Definition: png.h:2877
void set(bool on)
Set all bits to the specified state.
Definition: NodeMasks.h:742
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:158
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:943
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:406
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:554
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:452
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:769
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:936
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1383
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:722
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:759
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:430
GLdouble n
Definition: glcorearb.h:2007
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:591
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:351
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:942
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:771
void save(std::ostream &os) const
Definition: NodeMasks.h:567
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:835
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:504
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:309
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:726
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:496
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:336
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1399
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:981
OffMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:249
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:645
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:502
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:730
Index32 CountOn(Byte v)
Return the number of on bits in the given 8-bit value.
Definition: NodeMasks.h:55
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:812
Base class for the bit mask iterators.
Definition: NodeMasks.h:181
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:975
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:865
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:993
BaseMaskIterator & operator=(const BaseMaskIterator &iter)
Definition: NodeMasks.h:197
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:728
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:464
DenseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:281
DenseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1209
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:512
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:952
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:763
const RootNodeMask & operator|=(const RootNodeMask &other)
Definition: NodeMasks.h:1260
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1047
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:454
OffIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1181
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:724
BaseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1120
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:500
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:414
bool operator!=(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:195
RootNodeMask & operator=(const RootNodeMask &B)
Definition: NodeMasks.h:1100
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:720
bool operator==(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:194
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:352
BaseIterator & operator=(const BaseIterator &iter)
Definition: NodeMasks.h:1125
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1012
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1387
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:950
void set(bool on)
Set all bits to the specified state.
Definition: NodeMasks.h:964
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:574
const RootNodeMask & operator&=(const RootNodeMask &other)
Definition: NodeMasks.h:1252
RootNodeMask operator|(const RootNodeMask &other) const
Definition: NodeMasks.h:1277
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:924
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:828
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:957
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:334
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1028
bool operator!=(const NodeMask &other) const
Definition: NodeMasks.h:368
Index32 FindLowestOn(Byte v)
Return the least significant on bit of the given 8-bit value.
Definition: NodeMasks.h:112
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:519
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:350
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:721
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:748
GA_API const UT_StringHolder N
NodeMask & operator=(const NodeMask &other)
Assignment operator.
Definition: NodeMasks.h:342
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:995
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:944
unsigned char Byte
Definition: Types.h:66
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:714
#define SIZE
Definition: simple.C:40
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:338
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:753
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1032
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:822
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:948
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:867
void set(bool on)
Set all bits to the specified state.
Definition: NodeMasks.h:466
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:641
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:816
bool operator!=(const RootNodeMask &B) const
Definition: NodeMasks.h:1242
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:135
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:735
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:609
OnIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1153
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:946
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:440
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:560
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:438
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:696
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:510
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:490
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:708