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