HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
NodeMasks.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2017 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
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 <cassert>
39 #include <cstring>
40 #include <iostream>// for cout
41 #include <openvdb/Platform.h>
42 #include <openvdb/Types.h>
43 //#include <hboost/mpl/if.hpp>
44 //#include <strings.h> // for ffs
45 
46 namespace openvdb {
48 namespace OPENVDB_VERSION_NAME {
49 namespace util {
50 
51 /// Return the number of on bits in the given 8-bit value.
52 inline Index32
54 {
55  // Simple LUT:
56 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
57  static
58 #endif
59  const Byte numBits[256] = {
60 # define B2(n) n, n+1, n+1, n+2
61 # define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
62 # define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
63  B6(0), B6(1), B6(1), B6(2)
64  };
65  return numBits[v];
66 
67  // Sequentially clear least significant bits
68  //Index32 c;
69  //for (c = 0; v; c++) v &= v - 0x01U;
70  //return c;
71 
72  // This version is only fast on CPUs with fast "%" and "*" operations
73  //return (v * UINT64_C(0x200040008001) & UINT64_C(0x111111111111111)) % 0xF;
74 }
75 /// Return the number of off bits in the given 8-bit value.
76 inline Index32 CountOff(Byte v) { return CountOn(static_cast<Byte>(~v)); }
77 
78 /// Return the number of on bits in the given 32-bit value.
79 inline Index32
81 {
82  v = v - ((v >> 1) & 0x55555555U);
83  v = (v & 0x33333333U) + ((v >> 2) & 0x33333333U);
84  return (((v + (v >> 4)) & 0xF0F0F0FU) * 0x1010101U) >> 24;
85 }
86 
87 /// Return the number of off bits in the given 32-bit value.
88 inline Index32 CountOff(Index32 v) { return CountOn(~v); }
89 
90 /// Return the number of on bits in the given 64-bit value.
91 inline Index32
93 {
94  v = v - ((v >> 1) & UINT64_C(0x5555555555555555));
95  v = (v & UINT64_C(0x3333333333333333)) + ((v >> 2) & UINT64_C(0x3333333333333333));
96  return static_cast<Index32>(
97  (((v + (v >> 4)) & UINT64_C(0xF0F0F0F0F0F0F0F)) * UINT64_C(0x101010101010101)) >> 56);
98 }
99 
100 /// Return the number of off bits in the given 64-bit value.
101 inline Index32 CountOff(Index64 v) { return CountOn(~v); }
102 
103 /// Return the least significant on bit of the given 8-bit value.
104 inline Index32
106 {
107  assert(v);
108 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
109  static
110 #endif
111  const Byte DeBruijn[8] = {0, 1, 6, 2, 7, 5, 4, 3};
112  return DeBruijn[Byte((v & -v) * 0x1DU) >> 5];
113 }
114 
115 /// Return the least significant on bit of the given 32-bit value.
116 inline Index32
118 {
119  assert(v);
120  //return ffs(v);
121 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
122  static
123 #endif
124  const Byte DeBruijn[32] = {
125  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
126  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
127  };
128  return DeBruijn[Index32((v & -v) * 0x077CB531U) >> 27];
129 }
130 
131 /// Return the least significant on bit of the given 64-bit value.
132 inline Index32
134 {
135  assert(v);
136  //return ffsll(v);
137 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
138  static
139 #endif
140  const Byte DeBruijn[64] = {
141  0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
142  62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
143  63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
144  51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12,
145  };
146  return DeBruijn[Index64((v & -v) * UINT64_C(0x022FDD63CC95386D)) >> 58];
147 }
148 
149 /// Return the most significant on bit of the given 32-bit value.
150 inline Index32
152 {
153 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
154  static
155 #endif
156  const Byte DeBruijn[32] = {
157  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
158  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
159  };
160  v |= v >> 1; // first round down to one less than a power of 2
161  v |= v >> 2;
162  v |= v >> 4;
163  v |= v >> 8;
164  v |= v >> 16;
165  return DeBruijn[Index32(v * 0x07C4ACDDU) >> 27];
166 }
167 
168 
169 ////////////////////////////////////////
170 
171 
172 /// Base class for the bit mask iterators
173 template<typename NodeMask>
175 {
176 protected:
177  Index32 mPos; // bit position
178  const NodeMask* mParent; // this iterator can't change the parent_mask!
179 
180 public:
182  BaseMaskIterator(const BaseMaskIterator&) = default;
183  BaseMaskIterator(Index32 pos, const NodeMask* parent): mPos(pos), mParent(parent)
184  {
185  assert((parent == nullptr && pos == 0) || (parent != nullptr && pos <= NodeMask::SIZE));
186  }
187  bool operator==(const BaseMaskIterator &iter) const {return mPos == iter.mPos;}
188  bool operator!=(const BaseMaskIterator &iter) const {return mPos != iter.mPos;}
189  bool operator< (const BaseMaskIterator &iter) const {return mPos < iter.mPos;}
191  {
192  mPos = iter.mPos; mParent = iter.mParent; return *this;
193  }
194  Index32 offset() const { return mPos; }
195  Index32 pos() const { return mPos; }
196  bool test() const { assert(mPos <= NodeMask::SIZE); return (mPos != NodeMask::SIZE); }
197  operator bool() const { return this->test(); }
198 }; // class BaseMaskIterator
199 
200 
201 /// @note This happens to be a const-iterator!
202 template <typename NodeMask>
203 class OnMaskIterator: public BaseMaskIterator<NodeMask>
204 {
205 private:
207  using BaseType::mPos;//bit position;
208  using BaseType::mParent;//this iterator can't change the parent_mask!
209 public:
211  OnMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
212  void increment()
213  {
214  assert(mParent != nullptr);
215  mPos = mParent->findNextOn(mPos+1);
216  assert(mPos <= NodeMask::SIZE);
217  }
218  void increment(Index n) { while(n-- && this->next()) ; }
219  bool next()
220  {
221  this->increment();
222  return this->test();
223  }
224  bool operator*() const {return true;}
226  {
227  this->increment();
228  return *this;
229  }
230 }; // class OnMaskIterator
231 
232 
233 template <typename NodeMask>
234 class OffMaskIterator: public BaseMaskIterator<NodeMask>
235 {
236 private:
238  using BaseType::mPos;//bit position;
239  using BaseType::mParent;//this iterator can't change the parent_mask!
240 public:
242  OffMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
243  void increment()
244  {
245  assert(mParent != nullptr);
247  assert(mPos <= NodeMask::SIZE);
248  }
249  void increment(Index n) { while(n-- && this->next()) ; }
250  bool next()
251  {
252  this->increment();
253  return this->test();
254  }
255  bool operator*() const {return false;}
257  {
258  this->increment();
259  return *this;
260  }
261 }; // class OffMaskIterator
262 
263 
264 template <typename NodeMask>
265 class DenseMaskIterator: public BaseMaskIterator<NodeMask>
266 {
267 private:
269  using BaseType::mPos;//bit position;
270  using BaseType::mParent;//this iterator can't change the parent_mask!
271 
272 public:
274  DenseMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
275  void increment()
276  {
277  assert(mParent != nullptr);
278  mPos += 1;//careful - the increment might go beyond the end
279  assert(mPos<= NodeMask::SIZE);
280  }
281  void increment(Index n) { while(n-- && this->next()) ; }
282  bool next()
283  {
284  this->increment();
285  return this->test();
286  }
287  bool operator*() const {return mParent->isOn(mPos);}
289  {
290  this->increment();
291  return *this;
292  }
293 }; // class DenseMaskIterator
294 
295 
296 /// @brief Bit mask for the internal and leaf nodes of VDB. This
297 /// is a 64-bit implementation.
298 ///
299 /// @note A template specialization for Log2Dim=1 and Log2Dim=2 are
300 /// given below.
301 template<Index Log2Dim>
302 class NodeMask
303 {
304 public:
305  HBOOST_STATIC_ASSERT( Log2Dim>2 );
306 
307  static const Index32 LOG2DIM = Log2Dim;
308  static const Index32 DIM = 1<<Log2Dim;
309  static const Index32 SIZE = 1<<3*Log2Dim;
310  static const Index32 WORD_COUNT = SIZE >> 6;// 2^6=64
311  typedef Index64 Word;
312 
313 private:
314 
315  // The bits are represented as a linear array of Words, and the
316  // size of a Word is 32 or 64 bits depending on the platform.
317  // The BIT_MASK is defined as the number of bits in a Word - 1
318  //static const Index32 BIT_MASK = sizeof(void*) == 8 ? 63 : 31;
319  //static const Index32 LOG2WORD = BIT_MASK == 63 ? 6 : 5;
320  //static const Index32 WORD_COUNT = SIZE >> LOG2WORD;
321  //typedef hboost::mpl::if_c<BIT_MASK == 63, Index64, Index32>::type Word;
322 
323  Word mWords[WORD_COUNT];//only member data!
324 
325 public:
326  /// Default constructor sets all bits off
327  NodeMask() { this->setOff(); }
328  /// All bits are set to the specified state
329  NodeMask(bool on) { this->set(on); }
330  /// Copy constructor
331  NodeMask(const NodeMask &other) { *this = other; }
332  /// Destructor
334  /// Assignment operator
335  NodeMask& operator=(const NodeMask& other)
336  {
337  Index32 n = WORD_COUNT;
338  const Word* w2 = other.mWords;
339  for (Word* w1 = mWords; n--; ++w1, ++w2) *w1 = *w2;
340  return *this;
341  }
342 
346 
347  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
348  OnIterator endOn() const { return OnIterator(SIZE,this); }
349  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
350  OffIterator endOff() const { return OffIterator(SIZE,this); }
351  DenseIterator beginDense() const { return DenseIterator(0,this); }
352  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
353 
354  bool operator == (const NodeMask &other) const
355  {
356  int n = WORD_COUNT;
357  for (const Word *w1=mWords, *w2=other.mWords; n-- && *w1++ == *w2++;) ;
358  return n == -1;
359  }
360 
361  bool operator != (const NodeMask &other) const { return !(*this == other); }
362 
363  //
364  // Bitwise logical operations
365  //
366 
367  /// @brief Apply a functor to the words of the this and the other mask.
368  ///
369  /// @details An example that implements the "operator&=" method:
370  /// @code
371  /// struct Op { inline void operator()(W &w1, const W& w2) const { w1 &= w2; } };
372  /// @endcode
373  template<typename WordOp>
374  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
375  {
376  Word *w1 = mWords;
377  const Word *w2 = other.mWords;
378  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) op( *w1, *w2);
379  return *this;
380  }
381  template<typename WordOp>
382  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
383  {
384  Word *w1 = mWords;
385  const Word *w2 = other1.mWords, *w3 = other2.mWords;
386  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3) op( *w1, *w2, *w3);
387  return *this;
388  }
389  template<typename WordOp>
390  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
391  const WordOp& op)
392  {
393  Word *w1 = mWords;
394  const Word *w2 = other1.mWords, *w3 = other2.mWords, *w4 = other3.mWords;
395  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3, ++w4) op( *w1, *w2, *w3, *w4);
396  return *this;
397  }
398  /// @brief Bitwise intersection
399  const NodeMask& operator&=(const NodeMask& other)
400  {
401  Word *w1 = mWords;
402  const Word *w2 = other.mWords;
403  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= *w2;
404  return *this;
405  }
406  /// @brief Bitwise union
407  const NodeMask& operator|=(const NodeMask& other)
408  {
409  Word *w1 = mWords;
410  const Word *w2 = other.mWords;
411  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 |= *w2;
412  return *this;
413  }
414  /// @brief Bitwise difference
415  const NodeMask& operator-=(const NodeMask& other)
416  {
417  Word *w1 = mWords;
418  const Word *w2 = other.mWords;
419  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= ~*w2;
420  return *this;
421  }
422  /// @brief Bitwise XOR
423  const NodeMask& operator^=(const NodeMask& other)
424  {
425  Word *w1 = mWords;
426  const Word *w2 = other.mWords;
427  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 ^= *w2;
428  return *this;
429  }
430  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
431  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
432  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
433  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
434 
435  /// Return the byte size of this NodeMask
436  static Index32 memUsage() { return static_cast<Index32>(WORD_COUNT*sizeof(Word)); }
437  /// Return the total number of on bits
438  Index32 countOn() const
439  {
440  Index32 sum = 0, n = WORD_COUNT;
441  for (const Word* w = mWords; n--; ++w) sum += CountOn(*w);
442  return sum;
443  }
444  /// Return the total number of on bits
445  Index32 countOff() const { return SIZE-this->countOn(); }
446  /// Set the <i>n</i>th bit on
447  void setOn(Index32 n) {
448  assert( (n >> 6) < WORD_COUNT );
449  mWords[n >> 6] |= Word(1) << (n & 63);
450  }
451  /// Set the <i>n</i>th bit off
452  void setOff(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 to the specified state
457  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
458  /// Set all bits to the specified state
459  void set(bool on)
460  {
461  const Word state = on ? ~Word(0) : Word(0);
462  Index32 n = WORD_COUNT;
463  for (Word* w = mWords; n--; ++w) *w = state;
464  }
465  /// Set all bits on
466  void setOn()
467  {
468  Index32 n = WORD_COUNT;
469  for (Word* w = mWords; n--; ++w) *w = ~Word(0);
470  }
471  /// Set all bits off
472  void setOff()
473  {
474  Index32 n = WORD_COUNT;
475  for (Word* w = mWords; n--; ++w) *w = Word(0);
476  }
477  /// Toggle the state of the <i>n</i>th bit
478  void toggle(Index32 n) {
479  assert( (n >> 6) < WORD_COUNT );
480  mWords[n >> 6] ^= Word(1) << (n & 63);
481  }
482  /// Toggle the state of all bits in the mask
483  void toggle()
484  {
485  Index32 n = WORD_COUNT;
486  for (Word* w = mWords; n--; ++w) *w = ~*w;
487  }
488  /// Set the first bit on
489  void setFirstOn() { this->setOn(0); }
490  /// Set the last bit on
491  void setLastOn() { this->setOn(SIZE-1); }
492  /// Set the first bit off
493  void setFirstOff() { this->setOff(0); }
494  /// Set the last bit off
495  void setLastOff() { this->setOff(SIZE-1); }
496  /// Return @c true if the <i>n</i>th bit is on
497  bool isOn(Index32 n) const
498  {
499  assert( (n >> 6) < WORD_COUNT );
500  return 0 != (mWords[n >> 6] & (Word(1) << (n & 63)));
501  }
502  /// Return @c true if the <i>n</i>th bit is off
503  bool isOff(Index32 n) const {return !this->isOn(n); }
504  /// Return @c true if all the bits are on
505  bool isOn() const
506  {
507  int n = WORD_COUNT;
508  for (const Word *w = mWords; n-- && *w++ == ~Word(0);) ;
509  return n == -1;
510  }
511  /// Return @c true if all the bits are off
512  bool isOff() 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 bits are either all off OR all on.
519  /// @param isOn Takes on the values of all bits if the method
520  /// returns true - else it is undefined.
521  bool isConstant(bool &isOn) const
522  {
523  isOn = (mWords[0] == ~Word(0));//first word has all bits on
524  if ( !isOn && mWords[0] != Word(0)) return false;//early out
525  const Word *w = mWords + 1, *n = mWords + WORD_COUNT;
526  while( w<n && *w == mWords[0] ) ++w;
527  return w == n;
528  }
530  {
531  Index32 n = 0;
532  const Word* w = mWords;
533  for (; n<WORD_COUNT && !*w; ++w, ++n) ;
534  return n==WORD_COUNT ? SIZE : (n << 6) + FindLowestOn(*w);
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  }
543 
544  //@{
545  /// Return the <i>n</i>th word of the bit mask, for a word of arbitrary size.
546  template<typename WordT>
547  WordT getWord(Index n) const
548  {
549  assert(n*8*sizeof(WordT) < SIZE);
550  return reinterpret_cast<const WordT*>(mWords)[n];
551  }
552  template<typename WordT>
553  WordT& getWord(Index n)
554  {
555  assert(n*8*sizeof(WordT) < SIZE);
556  return reinterpret_cast<WordT*>(mWords)[n];
557  }
558  //@}
559 
560  void save(std::ostream& os) const
561  {
562  os.write(reinterpret_cast<const char*>(mWords), this->memUsage());
563  }
564  void load(std::istream& is) {
565  is.read(reinterpret_cast<char*>(mWords), this->memUsage());
566  }
567  void seek(std::istream& is) const {
568  is.seekg(this->memUsage(), std::ios_base::cur);
569  }
570  /// @brief simple print method for debugging
571  void printInfo(std::ostream& os=std::cout) const
572  {
573  os << "NodeMask: Dim=" << DIM << " Log2Dim=" << Log2Dim
574  << " Bit count=" << SIZE << " word count=" << WORD_COUNT << std::endl;
575  }
576  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const
577  {
578  const Index32 n=(SIZE>max_out ? max_out : SIZE);
579  for (Index32 i=0; i < n; ++i) {
580  if ( !(i & 63) )
581  os << "||";
582  else if ( !(i%8) )
583  os << "|";
584  os << this->isOn(i);
585  }
586  os << "|" << std::endl;
587  }
588  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const
589  {
590  this->printInfo(os);
591  this->printBits(os, max_out);
592  }
593 
595  {
596  Index32 n = start >> 6;//initiate
597  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
598  Index32 m = start & 63;
599  Word b = mWords[n];
600  if (b & (Word(1) << m)) return start;//simpel case: start is on
601  b &= ~Word(0) << m;// mask out lower bits
602  while(!b && ++n<WORD_COUNT) b = mWords[n];// find next none-zero word
603  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
604  }
605 
607  {
608  Index32 n = start >> 6;//initiate
609  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
610  Index32 m = start & 63;
611  Word b = ~mWords[n];
612  if (b & (Word(1) << m)) return start;//simpel case: start is on
613  b &= ~Word(0) << m;// mask out lower bits
614  while(!b && ++n<WORD_COUNT) b = ~mWords[n];// find next none-zero word
615  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
616  }
617 };// NodeMask
618 
619 
620 /// @brief Template specialization of NodeMask for Log2Dim=1, i.e. 2^3 nodes
621 template<>
622 class NodeMask<1>
623 {
624 public:
625 
626  static const Index32 LOG2DIM = 1;
627  static const Index32 DIM = 2;
628  static const Index32 SIZE = 8;
629  static const Index32 WORD_COUNT = 1;
630  typedef Byte Word;
631 
632 private:
633 
634  Byte mByte;//only member data!
635 
636 public:
637  /// Default constructor sets all bits off
638  NodeMask() : mByte(0x00U) {}
639  /// All bits are set to the specified state
640  NodeMask(bool on) : mByte(on ? 0xFFU : 0x00U) {}
641  /// Copy constructor
642  NodeMask(const NodeMask &other) : mByte(other.mByte) {}
643  /// Destructor
645  /// Assignment operator
646  void operator = (const NodeMask &other) { mByte = other.mByte; }
647 
651 
652  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
653  OnIterator endOn() const { return OnIterator(SIZE,this); }
654  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
655  OffIterator endOff() const { return OffIterator(SIZE,this); }
656  DenseIterator beginDense() const { return DenseIterator(0,this); }
657  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
658 
659  bool operator == (const NodeMask &other) const { return mByte == other.mByte; }
660 
661  bool operator != (const NodeMask &other) const {return mByte != other.mByte; }
662 
663  //
664  // Bitwise logical operations
665  //
666 
667  /// @brief Apply a functor to the words of the this and the other mask.
668  ///
669  /// @details An example that implements the "operator&=" method:
670  /// @code
671  /// struct Op { inline void operator()(Word &w1, const Word& w2) const { w1 &= w2; } };
672  /// @endcode
673  template<typename WordOp>
674  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
675  {
676  op(mByte, other.mByte);
677  return *this;
678  }
679  template<typename WordOp>
680  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
681  {
682  op(mByte, other1.mByte, other2.mByte);
683  return *this;
684  }
685  template<typename WordOp>
686  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
687  const WordOp& op)
688  {
689  op(mByte, other1.mByte, other2.mByte, other3.mByte);
690  return *this;
691  }
692  /// @brief Bitwise intersection
693  const NodeMask& operator&=(const NodeMask& other)
694  {
695  mByte &= other.mByte;
696  return *this;
697  }
698  /// @brief Bitwise union
699  const NodeMask& operator|=(const NodeMask& other)
700  {
701  mByte |= other.mByte;
702  return *this;
703  }
704  /// @brief Bitwise difference
705  const NodeMask& operator-=(const NodeMask& other)
706  {
707  mByte &= static_cast<Byte>(~other.mByte);
708  return *this;
709  }
710  /// @brief Bitwise XOR
711  const NodeMask& operator^=(const NodeMask& other)
712  {
713  mByte ^= other.mByte;
714  return *this;
715  }
716  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
717  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; 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  /// Return the byte size of this NodeMask
721  static Index32 memUsage() { return 1; }
722  /// Return the total number of on bits
723  Index32 countOn() const { return CountOn(mByte); }
724  /// Return the total number of on bits
725  Index32 countOff() const { return CountOff(mByte); }
726  /// Set the <i>n</i>th bit on
727  void setOn(Index32 n) {
728  assert( n < 8 );
729  mByte = mByte | static_cast<Byte>(0x01U << (n & 7));
730  }
731  /// Set the <i>n</i>th bit off
732  void setOff(Index32 n) {
733  assert( n < 8 );
734  mByte = mByte & static_cast<Byte>(~(0x01U << (n & 7)));
735  }
736  /// Set the <i>n</i>th bit to the specified state
737  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
738  /// Set all bits to the specified state
739  void set(bool on) { mByte = on ? 0xFFU : 0x00U; }
740  /// Set all bits on
741  void setOn() { mByte = 0xFFU; }
742  /// Set all bits off
743  void setOff() { mByte = 0x00U; }
744  /// Toggle the state of the <i>n</i>th bit
745  void toggle(Index32 n) {
746  assert( n < 8 );
747  mByte = mByte ^ static_cast<Byte>(0x01U << (n & 7));
748  }
749  /// Toggle the state of all bits in the mask
750  void toggle() { mByte = static_cast<Byte>(~mByte); }
751  /// Set the first bit on
752  void setFirstOn() { this->setOn(0); }
753  /// Set the last bit on
754  void setLastOn() { this->setOn(7); }
755  /// Set the first bit off
756  void setFirstOff() { this->setOff(0); }
757  /// Set the last bit off
758  void setLastOff() { this->setOff(7); }
759  /// Return true if the <i>n</i>th bit is on
760  bool isOn(Index32 n) const
761  {
762  assert( n < 8 );
763  return mByte & (0x01U << (n & 7));
764  }
765  /// Return true if the <i>n</i>th bit is off
766  bool isOff(Index32 n) const {return !this->isOn(n); }
767  /// Return true if all the bits are on
768  bool isOn() const { return mByte == 0xFFU; }
769  /// Return true if all the bits are off
770  bool isOff() const { return mByte == 0; }
771  /// Return @c true if bits are either all off OR all on.
772  /// @param isOn Takes on the values of all bits if the method
773  /// returns true - else it is undefined.
774  bool isConstant(bool &isOn) const
775  {
776  isOn = this->isOn();
777  return isOn || this->isOff();
778  }
779  Index32 findFirstOn() const { return mByte ? FindLowestOn(mByte) : 8; }
781  {
782  const Byte b = static_cast<Byte>(~mByte);
783  return b ? FindLowestOn(b) : 8;
784  }
785  /*
786  //@{
787  /// Return the <i>n</i>th word of the bit mask, for a word of arbitrary size.
788  /// @note This version assumes WordT=Byte and n=0!
789  template<typename WordT>
790  WordT getWord(Index n) const
791  {
792  HBOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
793  assert(n == 0);
794  return reinterpret_cast<WordT>(mByte);
795  }
796  template<typename WordT>
797  WordT& getWord(Index n)
798  {
799  HBOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
800  assert(n == 0);
801  return reinterpret_cast<WordT&>(mByte);
802  }
803  //@}
804  */
805  void save(std::ostream& os) const
806  {
807  os.write(reinterpret_cast<const char*>(&mByte), 1);
808  }
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  typedef Index64 Word;
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
1025  {
1026  os.write(reinterpret_cast<const char*>(&mWord), 8);
1027  }
1028  void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mWord), 8); }
1029  void seek(std::istream& is) const { is.seekg(8, std::ios_base::cur); }
1030  /// @brief simple print method for debugging
1031  void printInfo(std::ostream& os=std::cout) const
1032  {
1033  os << "NodeMask: Dim=4, Log2Dim=2, Bit count=64, Word count=1"<<std::endl;
1034  }
1035  void printBits(std::ostream& os=std::cout) const
1036  {
1037  os << "|";
1038  for (Index32 i=0; i < 64; ++i) {
1039  if ( !(i%8) ) os << "|";
1040  os << this->isOn(i);
1041  }
1042  os << "||" << std::endl;
1043  }
1044  void printAll(std::ostream& os=std::cout) const
1045  {
1046  this->printInfo(os);
1047  this->printBits(os);
1048  }
1049 
1051  {
1052  if (start>=64) return 64;
1053  const Word w = mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1054  return w ? FindLowestOn(w) : 64;
1055  }
1056 
1058  {
1059  if (start>=64) return 64;
1060  const Word w = ~mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1061  return w ? FindLowestOn(w) : 64;
1062  }
1063 
1064 };// NodeMask<2>
1065 
1066 
1067 // Unlike NodeMask above this RootNodeMask has a run-time defined size.
1068 // It is only included for backward compatibility and will likely be
1069 // deprecated in the future!
1070 // This class is 32-bit specefic, hence the use if Index32 vs Index!
1072 {
1073 protected:
1076 
1077 public:
1078  RootNodeMask(): mBitSize(0), mIntSize(0), mBits(nullptr) {}
1080  mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new Index32[mIntSize])
1081  {
1082  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1083  }
1086  {
1087  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1088  }
1089  ~RootNodeMask() {delete [] mBits;}
1090 
1091  void init(Index32 bit_size) {
1092  mBitSize = bit_size;
1093  mIntSize =((bit_size-1)>>5)+1;
1094  delete [] mBits;
1095  mBits = new Index32[mIntSize];
1096  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1097  }
1098 
1099  Index getBitSize() const {return mBitSize;}
1100 
1101  Index getIntSize() const {return mIntSize;}
1102 
1104  if (mBitSize!=B.mBitSize) {
1105  mBitSize=B.mBitSize;
1106  mIntSize=B.mIntSize;
1107  delete [] mBits;
1108  mBits = new Index32[mIntSize];
1109  }
1110  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1111  return *this;
1112  }
1113 
1115  {
1116  protected:
1117  Index32 mPos;//bit position
1119  const RootNodeMask* mParent;//this iterator can't change the parent_mask!
1120  public:
1121  BaseIterator() : mPos(0), mBitSize(0), mParent(nullptr) {}
1122  BaseIterator(const BaseIterator&) = default;
1124  mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) { assert(pos <= mBitSize); }
1125  bool operator==(const BaseIterator &iter) const {return mPos == iter.mPos;}
1126  bool operator!=(const BaseIterator &iter) const {return mPos != iter.mPos;}
1127  bool operator< (const BaseIterator &iter) const {return mPos < iter.mPos;}
1129  mPos = iter.mPos;
1130  mBitSize = iter.mBitSize;
1131  mParent = iter.mParent;
1132  return *this;
1133  }
1134 
1135  Index32 offset() const {return mPos;}
1136 
1137  Index32 pos() const {return mPos;}
1138 
1139  bool test() const {
1140  assert(mPos <= mBitSize);
1141  return (mPos != mBitSize);
1142  }
1143 
1144  operator bool() const {return this->test();}
1145  }; // class BaseIterator
1146 
1147  /// @note This happens to be a const-iterator!
1148  class OnIterator: public BaseIterator
1149  {
1150  protected:
1151  using BaseIterator::mPos;//bit position;
1152  using BaseIterator::mBitSize;//bit size;
1153  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1154  public:
1156  OnIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1157  void increment() {
1158  assert(mParent != nullptr);
1160  assert(mPos <= mBitSize);
1161  }
1163  for (Index i=0; i<n && this->next(); ++i) {}
1164  }
1165  bool next() {
1166  this->increment();
1167  return this->test();
1168  }
1169  bool operator*() const {return true;}
1171  this->increment();
1172  return *this;
1173  }
1174  }; // class OnIterator
1175 
1177  {
1178  protected:
1179  using BaseIterator::mPos;//bit position;
1180  using BaseIterator::mBitSize;//bit size;
1181  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1182  public:
1184  OffIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1185  void increment() {
1186  assert(mParent != nullptr);
1188  assert(mPos <= mBitSize);
1189  }
1191  for (Index i=0; i<n && this->next(); ++i) {}
1192  }
1193  bool next() {
1194  this->increment();
1195  return this->test();
1196  }
1197  bool operator*() const {return true;}
1199  this->increment();
1200  return *this;
1201  }
1202  }; // class OffIterator
1203 
1205  {
1206  protected:
1207  using BaseIterator::mPos;//bit position;
1208  using BaseIterator::mBitSize;//bit size;
1209  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1210  public:
1212  DenseIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1213  void increment() {
1214  assert(mParent != nullptr);
1215  mPos += 1;//carefull - the increament might go beyond the end
1216  assert(mPos<= mBitSize);
1217  }
1219  for (Index i=0; i<n && this->next(); ++i) {}
1220  }
1221  bool next() {
1222  this->increment();
1223  return this->test();
1224  }
1225  bool operator*() const {return mParent->isOn(mPos);}
1227  this->increment();
1228  return *this;
1229  }
1230  }; // class DenseIterator
1231 
1232  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
1233  OnIterator endOn() const { return OnIterator(mBitSize,this); }
1234  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
1235  OffIterator endOff() const { return OffIterator(mBitSize,this); }
1236  DenseIterator beginDense() const { return DenseIterator(0,this); }
1237  DenseIterator endDense() const { return DenseIterator(mBitSize,this); }
1238 
1239  bool operator == (const RootNodeMask &B) const {
1240  if (mBitSize != B.mBitSize) return false;
1241  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return false;
1242  return true;
1243  }
1244 
1245  bool operator != (const RootNodeMask &B) const {
1246  if (mBitSize != B.mBitSize) return true;
1247  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return true;
1248  return false;
1249  }
1250 
1251  //
1252  // Bitwise logical operations
1253  //
1254  RootNodeMask operator!() const { RootNodeMask m = *this; m.toggle(); return m; }
1255  const RootNodeMask& operator&=(const RootNodeMask& other) {
1256  assert(mIntSize == other.mIntSize);
1257  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1258  mBits[i] &= other.mBits[i];
1259  }
1260  for (Index32 i = other.mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
1261  return *this;
1262  }
1263  const RootNodeMask& operator|=(const RootNodeMask& other) {
1264  assert(mIntSize == other.mIntSize);
1265  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1266  mBits[i] |= other.mBits[i];
1267  }
1268  return *this;
1269  }
1270  const RootNodeMask& operator^=(const RootNodeMask& other) {
1271  assert(mIntSize == other.mIntSize);
1272  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1273  mBits[i] ^= other.mBits[i];
1274  }
1275  return *this;
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  RootNodeMask operator^(const RootNodeMask& other) const {
1284  RootNodeMask m(*this); m ^= other; return m;
1285  }
1286 
1287 
1289  return static_cast<Index32>(mIntSize*sizeof(Index32) + sizeof(*this));
1290  }
1291 
1292  Index32 countOn() const {
1293  assert(mBits);
1294  Index32 n=0;
1295  for (Index32 i=0; i< mIntSize; ++i) n += CountOn(mBits[i]);
1296  return n;
1297  }
1298 
1299  Index32 countOff() const { return mBitSize-this->countOn(); }
1300 
1301  void setOn(Index32 i) {
1302  assert(mBits);
1303  assert( (i>>5) < mIntSize);
1304  mBits[i>>5] |= 1<<(i&31);
1305  }
1306 
1307  void setOff(Index32 i) {
1308  assert(mBits);
1309  assert( (i>>5) < mIntSize);
1310  mBits[i>>5] &= ~(1<<(i&31));
1311  }
1312 
1313  void set(Index32 i, bool On) { On ? this->setOn(i) : this->setOff(i); }
1314 
1315  void setOn() {
1316  assert(mBits);
1317  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
1318  }
1319  void setOff() {
1320  assert(mBits);
1321  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1322  }
1323  void toggle(Index32 i) {
1324  assert(mBits);
1325  assert( (i>>5) < mIntSize);
1326  mBits[i>>5] ^= 1<<(i&31);
1327  }
1328  void toggle() {
1329  assert(mBits);
1330  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
1331  }
1332  void setFirstOn() { this->setOn(0); }
1333  void setLastOn() { this->setOn(mBitSize-1); }
1334  void setFirstOff() { this->setOff(0); }
1335  void setLastOff() { this->setOff(mBitSize-1); }
1336  bool isOn(Index32 i) const {
1337  assert(mBits);
1338  assert( (i>>5) < mIntSize);
1339  return ( mBits[i >> 5] & (1<<(i&31)) );
1340  }
1341  bool isOff(Index32 i) const {
1342  assert(mBits);
1343  assert( (i>>5) < mIntSize);
1344  return ( ~mBits[i >> 5] & (1<<(i&31)) );
1345  }
1346 
1347  bool isOn() const {
1348  if (!mBits) return false;//undefined is off
1349  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0xFFFFFFFF) return false;
1350  return true;
1351  }
1352 
1353  bool isOff() const {
1354  if (!mBits) return true;//undefined is off
1355  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0) return false;
1356  return true;
1357  }
1358 
1360  assert(mBits);
1361  Index32 i=0;
1362  while(!mBits[i]) if (++i == mIntSize) return mBitSize;//reached end
1363  return 32*i + FindLowestOn(mBits[i]);
1364  }
1365 
1367  assert(mBits);
1368  Index32 i=0;
1369  while(!(~mBits[i])) if (++i == mIntSize) return mBitSize;//reached end
1370  return 32*i + FindLowestOn(~mBits[i]);
1371  }
1372 
1373  void save(std::ostream& os) const {
1374  assert(mBits);
1375  os.write(reinterpret_cast<const char*>(mBits), mIntSize * sizeof(Index32));
1376  }
1377  void load(std::istream& is) {
1378  assert(mBits);
1379  is.read(reinterpret_cast<char*>(mBits), mIntSize * sizeof(Index32));
1380  }
1381  void seek(std::istream& is) const {
1382  assert(mBits);
1383  is.seekg(mIntSize * sizeof(Index32), std::ios_base::cur);
1384  }
1385  /// @brief simple print method for debugging
1386  void printInfo(std::ostream& os=std::cout) const {
1387  os << "RootNodeMask: Bit-size="<<mBitSize<<" Int-size="<<mIntSize<<std::endl;
1388  }
1389 
1390  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const {
1391  const Index32 n=(mBitSize>max_out?max_out:mBitSize);
1392  for (Index32 i=0; i < n; ++i) {
1393  if ( !(i&31) )
1394  os << "||";
1395  else if ( !(i%8) )
1396  os << "|";
1397  os << this->isOn(i);
1398  }
1399  os << "|" << std::endl;
1400  }
1401 
1402  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const {
1403  this->printInfo(os);
1404  this->printBits(os,max_out);
1405  }
1406 
1408  assert(mBits);
1409  Index32 n = start >> 5, m = start & 31;//initiate
1410  if (n>=mIntSize) return mBitSize; // check for out of bounds
1411  Index32 b = mBits[n];
1412  if (b & (1<<m)) return start;//simple case
1413  b &= 0xFFFFFFFF << m;// mask lower bits
1414  while(!b && ++n<mIntSize) b = mBits[n];// find next nonzero int
1415  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1416  }
1417 
1419  assert(mBits);
1420  Index32 n = start >> 5, m = start & 31;//initiate
1421  if (n>=mIntSize) return mBitSize; // check for out of bounds
1422  Index32 b = ~mBits[n];
1423  if (b & (1<<m)) return start;//simple case
1424  b &= 0xFFFFFFFF<<m;// mask lower bits
1425  while(!b && ++n<mIntSize) b = ~mBits[n];// find next nonzero int
1426  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1427  }
1428 
1429  Index32 memUsage() const {
1430  assert(mBits);
1431  return static_cast<Index32>(sizeof(Index32*)+(2+mIntSize)*sizeof(Index32));//in bytes
1432  }
1433 }; // class RootNodeMask
1434 
1435 } // namespace util
1436 } // namespace OPENVDB_VERSION_NAME
1437 } // namespace openvdb
1438 
1439 #endif // OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
1440 
1441 // Copyright (c) 2012-2017 DreamWorks Animation LLC
1442 // All rights reserved. This software is distributed under the
1443 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool operator==(const RootNodeMask &B) const
Definition: NodeMasks.h:1239
RootNodeMask operator^(const RootNodeMask &other) const
Definition: NodeMasks.h:1283
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:491
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1057
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:737
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:415
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1407
Index32 CountOff(Byte v)
Return the number of off bits in the given 8-bit value.
Definition: NodeMasks.h:76
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:438
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:594
bool operator==(const NodeMask &other) const
Definition: NodeMasks.h:354
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:918
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128
OnMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:211
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1418
const GLdouble * v
Definition: glcorearb.h:836
GLuint start
Definition: glcorearb.h:474
void seek(std::istream &is) const
Definition: NodeMasks.h:567
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:452
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:432
BaseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:183
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:436
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:699
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:770
RootNodeMask operator&(const RootNodeMask &other) const
Definition: NodeMasks.h:1277
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:1270
bool operator<(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:189
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1044
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:640
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:478
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
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:650
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:576
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:344
png_uint_32 i
Definition: png.h:2877
void set(bool on)
Set all bits to the specified state.
Definition: NodeMasks.h:739
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:151
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:943
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:399
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:547
Index32 countOff() 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:766
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:1386
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:719
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:756
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:423
GLdouble n
Definition: glcorearb.h:2007
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:588
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:942
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:768
void save(std::ostream &os) const
Definition: NodeMasks.h:560
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:497
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:302
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:723
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:489
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:329
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1402
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:981
OffMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:242
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:642
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:495
#define B6(n)
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:727
Index32 CountOn(Byte v)
Return the number of on bits in the given 8-bit value.
Definition: NodeMasks.h:53
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:174
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:190
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:725
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:457
DenseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:274
DenseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1212
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:505
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:952
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:875
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:760
const RootNodeMask & operator|=(const RootNodeMask &other)
Definition: NodeMasks.h:1263
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1050
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:447
OffIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1184
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:721
BaseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1123
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:493
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:407
bool operator!=(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:188
RootNodeMask & operator=(const RootNodeMask &B)
Definition: NodeMasks.h:1103
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:717
bool operator==(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:187
BaseIterator & operator=(const BaseIterator &iter)
Definition: NodeMasks.h:1128
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:1390
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:950
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:343
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:571
const RootNodeMask & operator&=(const RootNodeMask &other)
Definition: NodeMasks.h:1255
RootNodeMask operator|(const RootNodeMask &other) const
Definition: NodeMasks.h:1280
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:327
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1031
bool operator!=(const NodeMask &other) const
Definition: NodeMasks.h:361
Index32 FindLowestOn(Byte v)
Return the least significant on bit of the given 8-bit value.
Definition: NodeMasks.h:105
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:512
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:718
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:745
GA_API const UT_StringHolder N
NodeMask & operator=(const NodeMask &other)
Assignment operator.
Definition: NodeMasks.h:335
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:62
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:711
#define SIZE
Definition: simple.C:40
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:331
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:750
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1035
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
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:459
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:638
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:345
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:816
bool operator!=(const RootNodeMask &B) const
Definition: NodeMasks.h:1245
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:732
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:606
OnIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1156
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:946
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:433
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:553
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:431
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:693
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:503
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:483
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:705