OpenVDB  3.2.0
NodeMasks.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2016 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
34 
35 #ifndef OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
36 #define OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
37 
38 #include <cassert>
39 #include <cstring>
40 #include <iostream>// for cout
41 #include <openvdb/Platform.h>
42 #include <openvdb/Types.h>
43 //#include <boost/mpl/if.hpp>
44 //#include <strings.h> // for ffs
45 
46 namespace openvdb {
48 namespace OPENVDB_VERSION_NAME {
49 namespace util {
50 
52 inline Index32
54 {
55  // Simple LUT:
56 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
57  static
58 #endif
59  const Byte numBits[256] = {
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 }
76 inline Index32 CountOff(Byte v) { return CountOn(static_cast<Byte>(~v)); }
77 
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 
88 inline Index32 CountOff(Index32 v) { return CountOn(~v); }
89 
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 
101 inline Index32 CountOff(Index64 v) { return CountOn(~v); }
102 
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 
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 
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 
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 
170 
171 
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 public:
180  BaseMaskIterator() : mPos(NodeMask::SIZE), mParent(NULL) {}
181  BaseMaskIterator(Index32 pos,const NodeMask *parent) : mPos(pos), mParent(parent)
182  {
183  assert( (parent==NULL && pos==0 ) || (parent!=NULL && pos<=NodeMask::SIZE) );
184  }
185  bool operator==(const BaseMaskIterator &iter) const {return mPos == iter.mPos;}
186  bool operator!=(const BaseMaskIterator &iter) const {return mPos != iter.mPos;}
187  bool operator< (const BaseMaskIterator &iter) const {return mPos < iter.mPos;}
189  {
190  mPos = iter.mPos; mParent = iter.mParent; return *this;
191  }
192  Index32 offset() const {return mPos;}
193  Index32 pos() const {return mPos;}
194  bool test() const
195  {
196  assert(mPos <= NodeMask::SIZE);
197  return (mPos != NodeMask::SIZE);
198  }
199  operator bool() const {return this->test();}
200 }; // class BaseMaskIterator
201 
202 
204 template <typename NodeMask>
205 class OnMaskIterator: public BaseMaskIterator<NodeMask>
206 {
207 private:
209  using BaseType::mPos;//bit position;
210  using BaseType::mParent;//this iterator can't change the parent_mask!
211 public:
212  OnMaskIterator() : BaseType() {}
213  OnMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
214  void increment()
215  {
216  assert(mParent != NULL);
217  mPos = mParent->findNextOn(mPos+1);
218  assert(mPos <= NodeMask::SIZE);
219  }
220  void increment(Index n) { while(n-- && this->next()) ; }
221  bool next()
222  {
223  this->increment();
224  return this->test();
225  }
226  bool operator*() const {return true;}
228  {
229  this->increment();
230  return *this;
231  }
232 }; // class OnMaskIterator
233 
234 
235 template <typename NodeMask>
236 class OffMaskIterator: public BaseMaskIterator<NodeMask>
237 {
238 private:
240  using BaseType::mPos;//bit position;
241  using BaseType::mParent;//this iterator can't change the parent_mask!
242 public:
243  OffMaskIterator() : BaseType() {}
244  OffMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
245  void increment()
246  {
247  assert(mParent != NULL);
248  mPos=mParent->findNextOff(mPos+1);
249  assert(mPos <= NodeMask::SIZE);
250  }
251  void increment(Index n) { while(n-- && this->next()) ; }
252  bool next()
253  {
254  this->increment();
255  return this->test();
256  }
257  bool operator*() const {return false;}
259  {
260  this->increment();
261  return *this;
262  }
263 }; // class OffMaskIterator
264 
265 
266 template <typename NodeMask>
267 class DenseMaskIterator: public BaseMaskIterator<NodeMask>
268 {
269 private:
271  using BaseType::mPos;//bit position;
272  using BaseType::mParent;//this iterator can't change the parent_mask!
273 
274 public:
275  DenseMaskIterator() : BaseType() {}
276  DenseMaskIterator(Index32 pos,const NodeMask *parent) : BaseType(pos,parent) {}
277  void increment()
278  {
279  assert(mParent != NULL);
280  mPos += 1;//careful - the increment might go beyond the end
281  assert(mPos<= NodeMask::SIZE);
282  }
283  void increment(Index n) { while(n-- && this->next()) ; }
284  bool next()
285  {
286  this->increment();
287  return this->test();
288  }
289  bool operator*() const {return mParent->isOn(mPos);}
291  {
292  this->increment();
293  return *this;
294  }
295 }; // class DenseMaskIterator
296 
297 
303 template<Index Log2Dim>
304 class NodeMask
305 {
306 public:
307  BOOST_STATIC_ASSERT( Log2Dim>2 );
308 
309  static const Index32 LOG2DIM = Log2Dim;
310  static const Index32 DIM = 1<<Log2Dim;
311  static const Index32 SIZE = 1<<3*Log2Dim;
312  static const Index32 WORD_COUNT = SIZE >> 6;// 2^6=64
313  typedef Index64 Word;
314 
315 private:
316 
317  // The bits are represented as a linear array of Words, and the
318  // size of a Word is 32 or 64 bits depending on the platform.
319  // The BIT_MASK is defined as the number of bits in a Word - 1
320  //static const Index32 BIT_MASK = sizeof(void*) == 8 ? 63 : 31;
321  //static const Index32 LOG2WORD = BIT_MASK == 63 ? 6 : 5;
322  //static const Index32 WORD_COUNT = SIZE >> LOG2WORD;
323  //typedef boost::mpl::if_c<BIT_MASK == 63, Index64, Index32>::type Word;
324 
325  Word mWords[WORD_COUNT];//only member data!
326 
327 public:
329  NodeMask() { this->setOff(); }
331  NodeMask(bool on) { this->set(on); }
333  NodeMask(const NodeMask &other) { *this = other; }
337  NodeMask& operator=(const NodeMask& other)
338  {
339  Index32 n = WORD_COUNT;
340  const Word* w2 = other.mWords;
341  for (Word* w1 = mWords; n--; ++w1, ++w2) *w1 = *w2;
342  return *this;
343  }
344 
348 
349  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
350  OnIterator endOn() const { return OnIterator(SIZE,this); }
351  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
352  OffIterator endOff() const { return OffIterator(SIZE,this); }
353  DenseIterator beginDense() const { return DenseIterator(0,this); }
354  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
355 
356  bool operator == (const NodeMask &other) const
357  {
358  int n = WORD_COUNT;
359  for (const Word *w1=mWords, *w2=other.mWords; n-- && *w1++ == *w2++;) ;
360  return n == -1;
361  }
362 
363  bool operator != (const NodeMask &other) const { return !(*this == other); }
364 
365  //
366  // Bitwise logical operations
367  //
368 
375  template<typename WordOp>
376  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
377  {
378  Word *w1 = mWords;
379  const Word *w2 = other.mWords;
380  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) op( *w1, *w2);
381  return *this;
382  }
383  template<typename WordOp>
384  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
385  {
386  Word *w1 = mWords;
387  const Word *w2 = other1.mWords, *w3 = other2.mWords;
388  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3) op( *w1, *w2, *w3);
389  return *this;
390  }
391  template<typename WordOp>
392  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
393  const WordOp& op)
394  {
395  Word *w1 = mWords;
396  const Word *w2 = other1.mWords, *w3 = other2.mWords, *w4 = other3.mWords;
397  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2, ++w3, ++w4) op( *w1, *w2, *w3, *w4);
398  return *this;
399  }
401  const NodeMask& operator&=(const NodeMask& other)
402  {
403  Word *w1 = mWords;
404  const Word *w2 = other.mWords;
405  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= *w2;
406  return *this;
407  }
409  const NodeMask& operator|=(const NodeMask& other)
410  {
411  Word *w1 = mWords;
412  const Word *w2 = other.mWords;
413  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 |= *w2;
414  return *this;
415  }
417  const NodeMask& operator-=(const NodeMask& other)
418  {
419  Word *w1 = mWords;
420  const Word *w2 = other.mWords;
421  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 &= ~*w2;
422  return *this;
423  }
425  const NodeMask& operator^=(const NodeMask& other)
426  {
427  Word *w1 = mWords;
428  const Word *w2 = other.mWords;
429  for (Index32 n = WORD_COUNT; n--; ++w1, ++w2) *w1 ^= *w2;
430  return *this;
431  }
432  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
433  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
434  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
435  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
436 
438  static Index32 memUsage() { return static_cast<Index32>(WORD_COUNT*sizeof(Word)); }
440  Index32 countOn() const
441  {
442  Index32 sum = 0, n = WORD_COUNT;
443  for (const Word* w = mWords; n--; ++w) sum += CountOn(*w);
444  return sum;
445  }
447  Index32 countOff() const { return SIZE-this->countOn(); }
449  void setOn(Index32 n) {
450  assert( (n >> 6) < WORD_COUNT );
451  mWords[n >> 6] |= Word(1) << (n & 63);
452  }
454  void setOff(Index32 n) {
455  assert( (n >> 6) < WORD_COUNT );
456  mWords[n >> 6] &= ~(Word(1) << (n & 63));
457  }
459  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
461  void set(bool on)
462  {
463  const Word state = on ? ~Word(0) : Word(0);
464  Index32 n = WORD_COUNT;
465  for (Word* w = mWords; n--; ++w) *w = state;
466  }
468  void setOn()
469  {
470  Index32 n = WORD_COUNT;
471  for (Word* w = mWords; n--; ++w) *w = ~Word(0);
472  }
474  void setOff()
475  {
476  Index32 n = WORD_COUNT;
477  for (Word* w = mWords; n--; ++w) *w = Word(0);
478  }
480  void toggle(Index32 n) {
481  assert( (n >> 6) < WORD_COUNT );
482  mWords[n >> 6] ^= Word(1) << (n & 63);
483  }
485  void toggle()
486  {
487  Index32 n = WORD_COUNT;
488  for (Word* w = mWords; n--; ++w) *w = ~*w;
489  }
491  void setFirstOn() { this->setOn(0); }
493  void setLastOn() { this->setOn(SIZE-1); }
495  void setFirstOff() { this->setOff(0); }
497  void setLastOff() { this->setOff(SIZE-1); }
499  bool isOn(Index32 n) const
500  {
501  assert( (n >> 6) < WORD_COUNT );
502  return 0 != (mWords[n >> 6] & (Word(1) << (n & 63)));
503  }
505  bool isOff(Index32 n) const {return !this->isOn(n); }
507  bool isOn() const
508  {
509  int n = WORD_COUNT;
510  for (const Word *w = mWords; n-- && *w++ == ~Word(0);) ;
511  return n == -1;
512  }
514  bool isOff() const
515  {
516  int n = WORD_COUNT;
517  for (const Word *w = mWords; n-- && *w++ == Word(0);) ;
518  return n == -1;
519  }
523  bool isConstant(bool &isOn) const
524  {
525  isOn = (mWords[0] == ~Word(0));//first word has all bits on
526  if ( !isOn && mWords[0] != Word(0)) return false;//early out
527  const Word *w = mWords + 1, *n = mWords + WORD_COUNT;
528  while( w<n && *w == mWords[0] ) ++w;
529  return w == n;
530  }
532  {
533  Index32 n = 0;
534  const Word* w = mWords;
535  for (; n<WORD_COUNT && !*w; ++w, ++n) ;
536  return n==WORD_COUNT ? SIZE : (n << 6) + FindLowestOn(*w);
537  }
539  {
540  Index32 n = 0;
541  const Word* w = mWords;
542  for (; n<WORD_COUNT && !~*w; ++w, ++n) ;
543  return n==WORD_COUNT ? SIZE : (n << 6) + FindLowestOn(~*w);
544  }
545 
547  template<typename WordT>
549  WordT getWord(Index n) const
550  {
551  assert(n*8*sizeof(WordT) < SIZE);
552  return reinterpret_cast<const WordT*>(mWords)[n];
553  }
554  template<typename WordT>
555  WordT& getWord(Index n)
556  {
557  assert(n*8*sizeof(WordT) < SIZE);
558  return reinterpret_cast<WordT*>(mWords)[n];
559  }
561 
562  void save(std::ostream& os) const
563  {
564  os.write(reinterpret_cast<const char*>(mWords), this->memUsage());
565  }
566  void load(std::istream& is) {
567  is.read(reinterpret_cast<char*>(mWords), this->memUsage());
568  }
570  void printInfo(std::ostream& os=std::cout) const
571  {
572  os << "NodeMask: Dim=" << DIM << " Log2Dim=" << Log2Dim
573  << " Bit count=" << SIZE << " word count=" << WORD_COUNT << std::endl;
574  }
575  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const
576  {
577  const Index32 n=(SIZE>max_out ? max_out : SIZE);
578  for (Index32 i=0; i < n; ++i) {
579  if ( !(i & 63) )
580  os << "||";
581  else if ( !(i%8) )
582  os << "|";
583  os << this->isOn(i);
584  }
585  os << "|" << std::endl;
586  }
587  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const
588  {
589  this->printInfo(os);
590  this->printBits(os, max_out);
591  }
592 
594  {
595  Index32 n = start >> 6;//initiate
596  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
597  Index32 m = start & 63;
598  Word b = mWords[n];
599  if (b & (Word(1) << m)) return start;//simpel case: start is on
600  b &= ~Word(0) << m;// mask out lower bits
601  while(!b && ++n<WORD_COUNT) b = mWords[n];// find next none-zero word
602  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
603  }
604 
606  {
607  Index32 n = start >> 6;//initiate
608  if (n >= WORD_COUNT) return SIZE; // check for out of bounds
609  Index32 m = start & 63;
610  Word b = ~mWords[n];
611  if (b & (Word(1) << m)) return start;//simpel case: start is on
612  b &= ~Word(0) << m;// mask out lower bits
613  while(!b && ++n<WORD_COUNT) b = ~mWords[n];// find next none-zero word
614  return (!b ? SIZE : (n << 6) + FindLowestOn(b));//catch last word=0
615  }
616 };// NodeMask
617 
618 
620 template<>
621 class NodeMask<1>
622 {
623 public:
624 
625  static const Index32 LOG2DIM = 1;
626  static const Index32 DIM = 2;
627  static const Index32 SIZE = 8;
628  static const Index32 WORD_COUNT = 1;
629  typedef Byte Word;
630 
631 private:
632 
633  Byte mByte;//only member data!
634 
635 public:
637  NodeMask() : mByte(0x00U) {}
639  NodeMask(bool on) : mByte(on ? 0xFFU : 0x00U) {}
641  NodeMask(const NodeMask &other) : mByte(other.mByte) {}
645  void operator = (const NodeMask &other) { mByte = other.mByte; }
646 
650 
651  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
652  OnIterator endOn() const { return OnIterator(SIZE,this); }
653  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
654  OffIterator endOff() const { return OffIterator(SIZE,this); }
655  DenseIterator beginDense() const { return DenseIterator(0,this); }
656  DenseIterator endDense() const { return DenseIterator(SIZE,this); }
657 
658  bool operator == (const NodeMask &other) const { return mByte == other.mByte; }
659 
660  bool operator != (const NodeMask &other) const {return mByte != other.mByte; }
661 
662  //
663  // Bitwise logical operations
664  //
665 
672  template<typename WordOp>
673  const NodeMask& foreach(const NodeMask& other, const WordOp& op)
674  {
675  op(mByte, other.mByte);
676  return *this;
677  }
678  template<typename WordOp>
679  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const WordOp& op)
680  {
681  op(mByte, other1.mByte, other2.mByte);
682  return *this;
683  }
684  template<typename WordOp>
685  const NodeMask& foreach(const NodeMask& other1, const NodeMask& other2, const NodeMask& other3,
686  const WordOp& op)
687  {
688  op(mByte, other1.mByte, other2.mByte, other3.mByte);
689  return *this;
690  }
692  const NodeMask& operator&=(const NodeMask& other)
693  {
694  mByte &= other.mByte;
695  return *this;
696  }
698  const NodeMask& operator|=(const NodeMask& other)
699  {
700  mByte |= other.mByte;
701  return *this;
702  }
704  const NodeMask& operator-=(const NodeMask& other)
705  {
706  mByte &= static_cast<Byte>(~other.mByte);
707  return *this;
708  }
710  const NodeMask& operator^=(const NodeMask& other)
711  {
712  mByte ^= other.mByte;
713  return *this;
714  }
715  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
716  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; 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; }
720  static Index32 memUsage() { return 1; }
722  Index32 countOn() const { return CountOn(mByte); }
724  Index32 countOff() const { return CountOff(mByte); }
726  void setOn(Index32 n) {
727  assert( n < 8 );
728  mByte = mByte | static_cast<Byte>(0x01U << (n & 7));
729  }
731  void setOff(Index32 n) {
732  assert( n < 8 );
733  mByte = mByte & static_cast<Byte>(~(0x01U << (n & 7)));
734  }
736  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
738  void set(bool on) { mByte = on ? 0xFFU : 0x00U; }
740  void setOn() { mByte = 0xFFU; }
742  void setOff() { mByte = 0x00U; }
744  void toggle(Index32 n) {
745  assert( n < 8 );
746  mByte = mByte ^ static_cast<Byte>(0x01U << (n & 7));
747  }
749  void toggle() { mByte = static_cast<Byte>(~mByte); }
751  void setFirstOn() { this->setOn(0); }
753  void setLastOn() { this->setOn(7); }
755  void setFirstOff() { this->setOff(0); }
757  void setLastOff() { this->setOff(7); }
759  bool isOn(Index32 n) const
760  {
761  assert( n < 8 );
762  return mByte & (0x01U << (n & 7));
763  }
765  bool isOff(Index32 n) const {return !this->isOn(n); }
767  bool isOn() const { return mByte == 0xFFU; }
769  bool isOff() const { return mByte == 0; }
773  bool isConstant(bool &isOn) const
774  {
775  isOn = this->isOn();
776  return isOn || this->isOff();
777  }
778  Index32 findFirstOn() const { return mByte ? FindLowestOn(mByte) : 8; }
780  {
781  const Byte b = static_cast<Byte>(~mByte);
782  return b ? FindLowestOn(b) : 8;
783  }
784  /*
786  template<typename WordT>
789  WordT getWord(Index n) const
790  {
791  BOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
792  assert(n == 0);
793  return reinterpret_cast<WordT>(mByte);
794  }
795  template<typename WordT>
796  WordT& getWord(Index n)
797  {
798  BOOST_STATIC_ASSERT(sizeof(WordT) == sizeof(Byte));
799  assert(n == 0);
800  return reinterpret_cast<WordT&>(mByte);
801  }
803  */
804  void save(std::ostream& os) const
805  {
806  os.write(reinterpret_cast<const char*>(&mByte), 1);
807  }
808  void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mByte), 1); }
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 
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  typedef Index64 Word;
854 
855 private:
856 
857  Word mWord;//only member data!
858 
859 public:
861  NodeMask() : mWord(UINT64_C(0x00)) {}
863  NodeMask(bool on) : mWord(on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00)) {}
865  NodeMask(const NodeMask &other) : mWord(other.mWord) {}
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 
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  }
916  const NodeMask& operator&=(const NodeMask& other)
917  {
918  mWord &= other.mWord;
919  return *this;
920  }
922  const NodeMask& operator|=(const NodeMask& other)
923  {
924  mWord |= other.mWord;
925  return *this;
926  }
928  const NodeMask& operator-=(const NodeMask& other)
929  {
930  mWord &= ~other.mWord;
931  return *this;
932  }
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; }
944  static Index32 memUsage() { return 8; }
946  Index32 countOn() const { return CountOn(mWord); }
948  Index32 countOff() const { return CountOff(mWord); }
950  void setOn(Index32 n) {
951  assert( n < 64 );
952  mWord |= UINT64_C(0x01) << (n & 63);
953  }
955  void setOff(Index32 n) {
956  assert( n < 64 );
957  mWord &= ~(UINT64_C(0x01) << (n & 63));
958  }
960  void set(Index32 n, bool On) { On ? this->setOn(n) : this->setOff(n); }
962  void set(bool on) { mWord = on ? UINT64_C(0xFFFFFFFFFFFFFFFF) : UINT64_C(0x00); }
964  void setOn() { mWord = UINT64_C(0xFFFFFFFFFFFFFFFF); }
966  void setOff() { mWord = UINT64_C(0x00); }
968  void toggle(Index32 n) {
969  assert( n < 64 );
970  mWord ^= UINT64_C(0x01) << (n & 63);
971  }
973  void toggle() { mWord = ~mWord; }
975  void setFirstOn() { this->setOn(0); }
977  void setLastOn() { this->setOn(63); }
979  void setFirstOff() { this->setOff(0); }
981  void setLastOff() { this->setOff(63); }
983  bool isOn(Index32 n) const
984  {
985  assert( n < 64 );
986  return 0 != (mWord & (UINT64_C(0x01) << (n & 63)));
987  }
989  bool isOff(Index32 n) const {return !this->isOn(n); }
991  bool isOn() const { return mWord == UINT64_C(0xFFFFFFFFFFFFFFFF); }
993  bool isOff() const { return mWord == 0; }
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  }
1008  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  }
1022  void save(std::ostream& os) const
1023  {
1024  os.write(reinterpret_cast<const char*>(&mWord), 8);
1025  }
1026  void load(std::istream& is) { is.read(reinterpret_cast<char*>(&mWord), 8); }
1028  void printInfo(std::ostream& os=std::cout) const
1029  {
1030  os << "NodeMask: Dim=4, Log2Dim=2, Bit count=64, Word count=1"<<std::endl;
1031  }
1032  void printBits(std::ostream& os=std::cout) const
1033  {
1034  os << "|";
1035  for (Index32 i=0; i < 64; ++i) {
1036  if ( !(i%8) ) os << "|";
1037  os << this->isOn(i);
1038  }
1039  os << "||" << std::endl;
1040  }
1041  void printAll(std::ostream& os=std::cout) const
1042  {
1043  this->printInfo(os);
1044  this->printBits(os);
1045  }
1046 
1048  {
1049  if (start>=64) return 64;
1050  const Word w = mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1051  return w ? FindLowestOn(w) : 64;
1052  }
1053 
1055  {
1056  if (start>=64) return 64;
1057  const Word w = ~mWord & (UINT64_C(0xFFFFFFFFFFFFFFFF) << start);
1058  return w ? FindLowestOn(w) : 64;
1059  }
1060 
1061 };// NodeMask<2>
1062 
1063 
1064 // Unlike NodeMask above this RootNodeMask has a run-time defined size.
1065 // It is only included for backward compatibility and will likely be
1066 // deprecated in the future!
1067 // This class is 32-bit specefic, hence the use if Index32 vs Index!
1069 {
1070 protected:
1071  Index32 mBitSize, mIntSize;
1073 
1074 public:
1075  RootNodeMask(): mBitSize(0), mIntSize(0), mBits(NULL) {}
1077  mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new Index32[mIntSize])
1078  {
1079  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1080  }
1082  mBitSize(B.mBitSize), mIntSize(B.mIntSize), mBits(new Index32[mIntSize])
1083  {
1084  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1085  }
1086  ~RootNodeMask() {delete [] mBits;}
1087 
1088  void init(Index32 bit_size) {
1089  mBitSize = bit_size;
1090  mIntSize =((bit_size-1)>>5)+1;
1091  delete [] mBits;
1092  mBits = new Index32[mIntSize];
1093  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1094  }
1095 
1096  Index getBitSize() const {return mBitSize;}
1097 
1098  Index getIntSize() const {return mIntSize;}
1099 
1101  if (mBitSize!=B.mBitSize) {
1102  mBitSize=B.mBitSize;
1103  mIntSize=B.mIntSize;
1104  delete [] mBits;
1105  mBits = new Index32[mIntSize];
1106  }
1107  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
1108  return *this;
1109  }
1110 
1112  {
1113  protected:
1114  Index32 mPos;//bit position
1116  const RootNodeMask* mParent;//this iterator can't change the parent_mask!
1117  public:
1118  BaseIterator() : mPos(0), mBitSize(0), mParent(NULL) {}
1119  BaseIterator(Index32 pos,const RootNodeMask *parent)
1120  : mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) {
1121  assert( pos<=mBitSize );
1122  }
1123  bool operator==(const BaseIterator &iter) const {return mPos == iter.mPos;}
1124  bool operator!=(const BaseIterator &iter) const {return mPos != iter.mPos;}
1125  bool operator< (const BaseIterator &iter) const {return mPos < iter.mPos;}
1127  mPos = iter.mPos;
1128  mBitSize = iter.mBitSize;
1129  mParent = iter.mParent;
1130  return *this;
1131  }
1132 
1133  Index32 offset() const {return mPos;}
1134 
1135  Index32 pos() const {return mPos;}
1136 
1137  bool test() const {
1138  assert(mPos <= mBitSize);
1139  return (mPos != mBitSize);
1140  }
1141 
1142  operator bool() const {return this->test();}
1143  }; // class BaseIterator
1144 
1146  class OnIterator: public BaseIterator
1147  {
1148  protected:
1149  using BaseIterator::mPos;//bit position;
1150  using BaseIterator::mBitSize;//bit size;
1151  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1152  public:
1154  OnIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1155  void increment() {
1156  assert(mParent!=NULL);
1157  mPos=mParent->findNextOn(mPos+1);
1158  assert(mPos <= mBitSize);
1159  }
1160  void increment(Index n) {
1161  for (Index i=0; i<n && this->next(); ++i) {}
1162  }
1163  bool next() {
1164  this->increment();
1165  return this->test();
1166  }
1167  bool operator*() const {return true;}
1168  OnIterator& operator++() {
1169  this->increment();
1170  return *this;
1171  }
1172  }; // class OnIterator
1173 
1174  class OffIterator: public BaseIterator
1175  {
1176  protected:
1177  using BaseIterator::mPos;//bit position;
1178  using BaseIterator::mBitSize;//bit size;
1179  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1180  public:
1182  OffIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1183  void increment() {
1184  assert(mParent!=NULL);
1185  mPos=mParent->findNextOff(mPos+1);
1186  assert(mPos <= mBitSize);
1187  }
1188  void increment(Index n) {
1189  for (Index i=0; i<n && this->next(); ++i) {}
1190  }
1191  bool next() {
1192  this->increment();
1193  return this->test();
1194  }
1195  bool operator*() const {return true;}
1196  OffIterator& operator++() {
1197  this->increment();
1198  return *this;
1199  }
1200  }; // class OffIterator
1201 
1202  class DenseIterator: public BaseIterator
1203  {
1204  protected:
1205  using BaseIterator::mPos;//bit position;
1206  using BaseIterator::mBitSize;//bit size;
1207  using BaseIterator::mParent;//this iterator can't change the parent_mask!
1208  public:
1210  DenseIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
1211  void increment() {
1212  assert(mParent!=NULL);
1213  mPos += 1;//carefull - the increament might go beyond the end
1214  assert(mPos<= mBitSize);
1215  }
1216  void increment(Index n) {
1217  for (Index i=0; i<n && this->next(); ++i) {}
1218  }
1219  bool next() {
1220  this->increment();
1221  return this->test();
1222  }
1223  bool operator*() const {return mParent->isOn(mPos);}
1224  DenseIterator& operator++() {
1225  this->increment();
1226  return *this;
1227  }
1228  }; // class DenseIterator
1229 
1230  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
1231  OnIterator endOn() const { return OnIterator(mBitSize,this); }
1232  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
1233  OffIterator endOff() const { return OffIterator(mBitSize,this); }
1234  DenseIterator beginDense() const { return DenseIterator(0,this); }
1235  DenseIterator endDense() const { return DenseIterator(mBitSize,this); }
1236 
1237  bool operator == (const RootNodeMask &B) const {
1238  if (mBitSize != B.mBitSize) return false;
1239  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return false;
1240  return true;
1241  }
1242 
1243  bool operator != (const RootNodeMask &B) const {
1244  if (mBitSize != B.mBitSize) return true;
1245  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return true;
1246  return false;
1247  }
1248 
1249  //
1250  // Bitwise logical operations
1251  //
1252  RootNodeMask operator!() const { RootNodeMask m = *this; m.toggle(); return m; }
1253  const RootNodeMask& operator&=(const RootNodeMask& other) {
1254  assert(mIntSize == other.mIntSize);
1255  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1256  mBits[i] &= other.mBits[i];
1257  }
1258  for (Index32 i = other.mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
1259  return *this;
1260  }
1261  const RootNodeMask& operator|=(const RootNodeMask& other) {
1262  assert(mIntSize == other.mIntSize);
1263  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1264  mBits[i] |= other.mBits[i];
1265  }
1266  return *this;
1267  }
1268  const RootNodeMask& operator^=(const RootNodeMask& other) {
1269  assert(mIntSize == other.mIntSize);
1270  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
1271  mBits[i] ^= other.mBits[i];
1272  }
1273  return *this;
1274  }
1275  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  RootNodeMask operator^(const RootNodeMask& other) const {
1282  RootNodeMask m(*this); m ^= other; return m;
1283  }
1284 
1285 
1287  return static_cast<Index32>(mIntSize*sizeof(Index32) + sizeof(*this));
1288  }
1289 
1290  Index32 countOn() const {
1291  assert(mBits);
1292  Index32 n=0;
1293  for (Index32 i=0; i< mIntSize; ++i) n += CountOn(mBits[i]);
1294  return n;
1295  }
1296 
1297  Index32 countOff() const { return mBitSize-this->countOn(); }
1298 
1299  void setOn(Index32 i) {
1300  assert(mBits);
1301  assert( (i>>5) < mIntSize);
1302  mBits[i>>5] |= 1<<(i&31);
1303  }
1304 
1305  void setOff(Index32 i) {
1306  assert(mBits);
1307  assert( (i>>5) < mIntSize);
1308  mBits[i>>5] &= ~(1<<(i&31));
1309  }
1310 
1311  void set(Index32 i, bool On) { On ? this->setOn(i) : this->setOff(i); }
1312 
1313  void setOn() {
1314  assert(mBits);
1315  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
1316  }
1317  void setOff() {
1318  assert(mBits);
1319  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
1320  }
1321  void toggle(Index32 i) {
1322  assert(mBits);
1323  assert( (i>>5) < mIntSize);
1324  mBits[i>>5] ^= 1<<(i&31);
1325  }
1326  void toggle() {
1327  assert(mBits);
1328  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
1329  }
1330  void setFirstOn() { this->setOn(0); }
1331  void setLastOn() { this->setOn(mBitSize-1); }
1332  void setFirstOff() { this->setOff(0); }
1333  void setLastOff() { this->setOff(mBitSize-1); }
1334  bool isOn(Index32 i) const {
1335  assert(mBits);
1336  assert( (i>>5) < mIntSize);
1337  return ( mBits[i >> 5] & (1<<(i&31)) );
1338  }
1339  bool isOff(Index32 i) const {
1340  assert(mBits);
1341  assert( (i>>5) < mIntSize);
1342  return ( ~mBits[i >> 5] & (1<<(i&31)) );
1343  }
1344 
1345  bool isOn() const {
1346  if (!mBits) return false;//undefined is off
1347  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0xFFFFFFFF) return false;
1348  return true;
1349  }
1350 
1351  bool isOff() const {
1352  if (!mBits) return true;//undefined is off
1353  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0) return false;
1354  return true;
1355  }
1356 
1358  assert(mBits);
1359  Index32 i=0;
1360  while(!mBits[i]) if (++i == mIntSize) return mBitSize;//reached end
1361  return 32*i + FindLowestOn(mBits[i]);
1362  }
1363 
1365  assert(mBits);
1366  Index32 i=0;
1367  while(!(~mBits[i])) if (++i == mIntSize) return mBitSize;//reached end
1368  return 32*i + FindLowestOn(~mBits[i]);
1369  }
1370 
1371  void save(std::ostream& os) const {
1372  assert(mBits);
1373  os.write((const char *)mBits,mIntSize*sizeof(Index32));
1374  }
1375  void load(std::istream& is) {
1376  assert(mBits);
1377  is.read((char *)mBits,mIntSize*sizeof(Index32));
1378  }
1380  void printInfo(std::ostream& os=std::cout) const {
1381  os << "RootNodeMask: Bit-size="<<mBitSize<<" Int-size="<<mIntSize<<std::endl;
1382  }
1383 
1384  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const {
1385  const Index32 n=(mBitSize>max_out?max_out:mBitSize);
1386  for (Index32 i=0; i < n; ++i) {
1387  if ( !(i&31) )
1388  os << "||";
1389  else if ( !(i%8) )
1390  os << "|";
1391  os << this->isOn(i);
1392  }
1393  os << "|" << std::endl;
1394  }
1395 
1396  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const {
1397  this->printInfo(os);
1398  this->printBits(os,max_out);
1399  }
1400 
1401  Index32 findNextOn(Index32 start) const {
1402  assert(mBits);
1403  Index32 n = start >> 5, m = start & 31;//initiate
1404  if (n>=mIntSize) return mBitSize; // check for out of bounds
1405  Index32 b = mBits[n];
1406  if (b & (1<<m)) return start;//simple case
1407  b &= 0xFFFFFFFF << m;// mask lower bits
1408  while(!b && ++n<mIntSize) b = mBits[n];// find next nonzero int
1409  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1410  }
1411 
1412  Index32 findNextOff(Index32 start) const {
1413  assert(mBits);
1414  Index32 n = start >> 5, m = start & 31;//initiate
1415  if (n>=mIntSize) return mBitSize; // check for out of bounds
1416  Index32 b = ~mBits[n];
1417  if (b & (1<<m)) return start;//simple case
1418  b &= 0xFFFFFFFF<<m;// mask lower bits
1419  while(!b && ++n<mIntSize) b = ~mBits[n];// find next nonzero int
1420  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
1421  }
1422 
1423  Index32 memUsage() const {
1424  assert(mBits);
1425  return static_cast<Index32>(sizeof(Index32*)+(2+mIntSize)*sizeof(Index32));//in bytes
1426  }
1427 }; // class RootNodeMask
1428 
1429 } // namespace util
1430 } // namespace OPENVDB_VERSION_NAME
1431 } // namespace openvdb
1432 
1433 #endif // OPENVDB_UTIL_NODEMASKS_HAS_BEEN_INCLUDED
1434 
1435 // Copyright (c) 2012-2016 DreamWorks Animation LLC
1436 // All rights reserved. This software is distributed under the
1437 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:523
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:637
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:767
void increment(Index n)
Definition: NodeMasks.h:251
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:934
bool next()
Definition: NodeMasks.h:1191
DenseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1210
void increment()
Definition: NodeMasks.h:214
Index32 offset() const
Definition: NodeMasks.h:1133
OnIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1154
DenseIterator endDense() const
Definition: NodeMasks.h:656
OnMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:213
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:942
void setOn()
Definition: NodeMasks.h:1313
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:648
Index32 FindLowestOn(Index64 v)
Return the least significant on bit of the given 64-bit value.
Definition: NodeMasks.h:133
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:710
bool operator*() const
Definition: NodeMasks.h:1167
DenseIterator endDense() const
Definition: NodeMasks.h:880
Definition: NodeMasks.h:1068
void increment()
Definition: NodeMasks.h:1155
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:718
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:872
bool operator==(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:185
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:401
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1401
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:991
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:447
DenseIterator endDense() const
Definition: NodeMasks.h:1235
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:417
void toggle()
Definition: NodeMasks.h:1326
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:345
void setOn(Index32 i)
Definition: NodeMasks.h:1299
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1380
void increment(Index n)
Definition: NodeMasks.h:1216
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:865
DenseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:276
Index32 mBitSize
Definition: NodeMasks.h:1071
void setOff()
Set all bits off.
Definition: NodeMasks.h:474
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:720
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:641
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:975
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:950
void load(std::istream &is)
Definition: NodeMasks.h:566
Index getBitSize() const
Definition: NodeMasks.h:1096
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:151
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:593
Index32 findFirstOff() const
Definition: NodeMasks.h:538
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:493
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:751
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:726
OffIterator & operator++()
Definition: NodeMasks.h:1196
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:948
DenseIterator beginDense() const
Definition: NodeMasks.h:353
void save(std::ostream &os) const
Definition: NodeMasks.h:804
void increment(Index n)
Definition: NodeMasks.h:220
Index32 mPos
Definition: NodeMasks.h:1114
Index64 Word
Definition: NodeMasks.h:853
void setFirstOn()
Definition: NodeMasks.h:1330
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:692
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:944
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:973
void load(std::istream &is)
Definition: NodeMasks.h:808
const NodeMask & operator&=(const NodeMask &other)
Bitwise intersection.
Definition: NodeMasks.h:916
NodeMask & operator=(const NodeMask &other)
Assignment operator.
Definition: NodeMasks.h:337
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:749
OffIterator endOff() const
Definition: NodeMasks.h:352
bool next()
Definition: NodeMasks.h:221
const RootNodeMask & operator|=(const RootNodeMask &other)
Definition: NodeMasks.h:1261
bool next()
Definition: NodeMasks.h:284
Index32 memUsage() const
Definition: NodeMasks.h:1423
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:605
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:724
void save(std::ostream &os) const
Definition: NodeMasks.h:1022
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:731
void setFirstOn()
Set the first bit on.
Definition: NodeMasks.h:491
bool operator==(const BaseIterator &iter) const
Definition: NodeMasks.h:1123
RootNodeMask(const RootNodeMask &B)
Definition: NodeMasks.h:1081
void load(std::istream &is)
Definition: NodeMasks.h:1026
const NodeMask & operator^=(const NodeMask &other)
Bitwise XOR.
Definition: NodeMasks.h:425
Index32 * mBits
Definition: NodeMasks.h:1072
NodeMask operator!() const
Definition: NodeMasks.h:432
bool test() const
Definition: NodeMasks.h:1137
const RootNodeMask * mParent
Definition: NodeMasks.h:1116
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:716
bool operator*() const
Definition: NodeMasks.h:226
bool operator!=(const BaseIterator &iter) const
Definition: NodeMasks.h:1124
Index32 mIntSize
Definition: NodeMasks.h:1071
NodeMask operator!() const
Definition: NodeMasks.h:939
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:497
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:955
bool next()
Definition: NodeMasks.h:1219
Index32 mBitSize
Definition: NodeMasks.h:1115
#define B6(n)
OffIterator beginOff() const
Definition: NodeMasks.h:1232
OnIterator beginOn() const
Definition: NodeMasks.h:875
NodeMask operator!() const
Definition: NodeMasks.h:715
bool isOff(Index32 i) const
Definition: NodeMasks.h:1339
OnIterator endOn() const
Definition: NodeMasks.h:876
OffIterator beginOff() const
Definition: NodeMasks.h:351
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:434
Index32 CountOff(Index64 v)
Return the number of off bits in the given 64-bit value.
Definition: NodeMasks.h:101
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:977
Index32 Index
Definition: Types.h:58
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:480
Index32 findFirstOn() const
Definition: NodeMasks.h:1001
OnIterator beginOn() const
Definition: NodeMasks.h:651
void increment(Index n)
Definition: NodeMasks.h:283
OnIterator endOn() const
Definition: NodeMasks.h:652
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:940
bool operator!=(const BaseMaskIterator &iter) const
Definition: NodeMasks.h:186
Index32 findFirstOn() const
Definition: NodeMasks.h:778
Index32 findFirstOff() const
Definition: NodeMasks.h:1364
Index getIntSize() const
Definition: NodeMasks.h:1098
uint64_t Index64
Definition: Types.h:57
void increment(Index n)
Definition: NodeMasks.h:1160
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:575
bool operator<(const Tuple< SIZE, T0 > &t0, const Tuple< SIZE, T1 > &t1)
Definition: Tuple.h:158
DenseIterator beginDense() const
Definition: NodeMasks.h:1234
const RootNodeMask & operator^=(const RootNodeMask &other)
Definition: NodeMasks.h:1268
bool isOn() const
Definition: NodeMasks.h:1345
#define OPENVDB_VERSION_NAME
Definition: version.h:43
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:514
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:1028
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:499
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:647
void setLastOn()
Set the last bit on.
Definition: NodeMasks.h:753
RootNodeMask operator|(const RootNodeMask &other) const
Definition: NodeMasks.h:1278
OffMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:244
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:639
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:704
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:993
Index32 mPos
Definition: NodeMasks.h:177
Index32 findFirstOn() const
Definition: NodeMasks.h:531
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:810
OnIterator endOn() const
Definition: NodeMasks.h:350
OnMaskIterator< NodeMask > OnIterator
Definition: NodeMasks.h:871
BaseMaskIterator(Index32 pos, const NodeMask *parent)
Definition: NodeMasks.h:181
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:863
const NodeMask & operator-=(const NodeMask &other)
Bitwise difference.
Definition: NodeMasks.h:928
bool operator*() const
Definition: NodeMasks.h:1195
bool isOff() const
Return true if all the bits are off.
Definition: NodeMasks.h:769
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:440
Index32 getMemUsage() const
Definition: NodeMasks.h:1286
bool next()
Definition: NodeMasks.h:1163
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:587
void load(std::istream &is)
Definition: NodeMasks.h:1375
RootNodeMask operator&(const RootNodeMask &other) const
Definition: NodeMasks.h:1275
OffMaskIterator< NodeMask > OffIterator
Definition: NodeMasks.h:346
OnIterator endOn() const
Definition: NodeMasks.h:1231
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:304
Index32 findFirstOn() const
Definition: NodeMasks.h:1357
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:757
void increment()
Definition: NodeMasks.h:277
void increment()
Definition: NodeMasks.h:1211
Definition: Exceptions.h:39
bool operator*() const
Definition: NodeMasks.h:257
uint32_t Index32
Definition: Types.h:56
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:549
void setLastOff()
Set the last bit off.
Definition: NodeMasks.h:981
RootNodeMask operator^(const RootNodeMask &other) const
Definition: NodeMasks.h:1281
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:946
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:409
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:997
const RootNodeMask & operator&=(const RootNodeMask &other)
Definition: NodeMasks.h:1253
DenseIterator endDense() const
Definition: NodeMasks.h:354
Index64 Word
Definition: NodeMasks.h:313
OnMaskIterator()
Definition: NodeMasks.h:212
void setOn()
Set all bits on.
Definition: NodeMasks.h:964
void increment()
Definition: NodeMasks.h:1183
Byte Word
Definition: NodeMasks.h:629
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:722
Index32 CountOn(Index64 v)
Return the number of on bits in the given 64-bit value.
Definition: NodeMasks.h:92
BaseIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1119
Index32 countOn() const
Definition: NodeMasks.h:1290
void setOff()
Set all bits off.
Definition: NodeMasks.h:742
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1016
BaseMaskIterator()
Definition: NodeMasks.h:180
void setOn()
Set all bits on.
Definition: NodeMasks.h:740
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:941
OffIterator(Index32 pos, const RootNodeMask *parent)
Definition: NodeMasks.h:1182
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:505
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:814
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:438
BaseIterator()
Definition: NodeMasks.h:1118
Definition: NodeMasks.h:267
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:329
Index32 findFirstOff() const
Definition: NodeMasks.h:779
~NodeMask()
Destructor.
Definition: NodeMasks.h:643
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:773
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:820
OffIterator endOff() const
Definition: NodeMasks.h:654
OffMaskIterator()
Definition: NodeMasks.h:243
RootNodeMask operator!() const
Definition: NodeMasks.h:1252
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:449
Index32 findFirstOff() const
Definition: NodeMasks.h:1002
void init(Index32 bit_size)
Definition: NodeMasks.h:1088
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:347
WordT getWord(Index n) const
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:1010
void printAll(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1041
void setOff()
Set all bits off.
Definition: NodeMasks.h:966
BaseMaskIterator & operator=(const BaseMaskIterator &iter)
Definition: NodeMasks.h:188
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:495
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:698
NodeMask operator|(const NodeMask &other) const
Definition: NodeMasks.h:717
void toggle()
Toggle the state of all bits in the mask.
Definition: NodeMasks.h:485
void printAll(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1396
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
~NodeMask()
Destructor.
Definition: NodeMasks.h:335
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:755
void printBits(std::ostream &os=std::cout) const
Definition: NodeMasks.h:1032
bool operator*() const
Definition: NodeMasks.h:1223
OnIterator()
Definition: NodeMasks.h:1153
OnIterator beginOn() const
Definition: NodeMasks.h:349
void save(std::ostream &os) const
Definition: NodeMasks.h:1371
~NodeMask()
Destructor.
Definition: NodeMasks.h:867
BaseIterator & operator=(const BaseIterator &iter)
Definition: NodeMasks.h:1126
Index32 pos() const
Definition: NodeMasks.h:193
OffIterator endOff() const
Definition: NodeMasks.h:878
NodeMask(bool on)
All bits are set to the specified state.
Definition: NodeMasks.h:331
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1054
void setFirstOff()
Definition: NodeMasks.h:1332
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:968
void increment(Index n)
Definition: NodeMasks.h:1188
Index32 offset() const
Definition: NodeMasks.h:192
DenseMaskIterator & operator++()
Definition: NodeMasks.h:290
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:454
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:759
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:744
const NodeMask & operator|=(const NodeMask &other)
Bitwise union.
Definition: NodeMasks.h:922
RootNodeMask & operator=(const RootNodeMask &B)
Definition: NodeMasks.h:1100
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition: Vec3.h:458
void setFirstOff()
Set the first bit off.
Definition: NodeMasks.h:979
OnMaskIterator & operator++()
Definition: NodeMasks.h:227
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:983
void setOff(Index32 i)
Definition: NodeMasks.h:1305
Index32 countOff() const
Definition: NodeMasks.h:1297
unsigned char Byte
Definition: Types.h:63
void setLastOn()
Definition: NodeMasks.h:1331
DenseIterator beginDense() const
Definition: NodeMasks.h:879
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:649
WordT & getWord(Index n)
Return the nth word of the bit mask, for a word of arbitrary size.
Definition: NodeMasks.h:555
NodeMask(const NodeMask &other)
Copy constructor.
Definition: NodeMasks.h:333
Definition: NodeMasks.h:205
bool isOff() const
Definition: NodeMasks.h:1351
OffIterator beginOff() const
Definition: NodeMasks.h:653
DenseIterator beginDense() const
Definition: NodeMasks.h:655
Definition: NodeMasks.h:236
void toggle(Index32 i)
Definition: NodeMasks.h:1321
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:873
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:989
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
void setLastOff()
Definition: NodeMasks.h:1333
RootNodeMask(Index32 bit_size)
Definition: NodeMasks.h:1076
void setOn()
Set all bits on.
Definition: NodeMasks.h:468
DenseMaskIterator()
Definition: NodeMasks.h:275
Index32 pos() const
Definition: NodeMasks.h:1135
bool isOn(Index32 i) const
Definition: NodeMasks.h:1334
void save(std::ostream &os) const
Definition: NodeMasks.h:562
OnIterator beginOn() const
Definition: NodeMasks.h:1230
OffMaskIterator & operator++()
Definition: NodeMasks.h:258
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:826
void printInfo(std::ostream &os=std::cout) const
simple print method for debugging
Definition: NodeMasks.h:570
Index32 findNextOff(Index32 start) const
Definition: NodeMasks.h:1412
NodeMask operator&(const NodeMask &other) const
Definition: NodeMasks.h:433
OffIterator beginOff() const
Definition: NodeMasks.h:877
RootNodeMask()
Definition: NodeMasks.h:1075
NodeMask()
Default constructor sets all bits off.
Definition: NodeMasks.h:861
bool isOn() const
Return true if all the bits are on.
Definition: NodeMasks.h:507
Index32 findNextOn(Index32 start) const
Definition: NodeMasks.h:1047
OffIterator endOff() const
Definition: NodeMasks.h:1233
const NodeMask * mParent
Definition: NodeMasks.h:178
bool operator*() const
Definition: NodeMasks.h:289
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:765
OffIterator()
Definition: NodeMasks.h:1181
DenseIterator & operator++()
Definition: NodeMasks.h:1224
bool next()
Definition: NodeMasks.h:252
OnIterator & operator++()
Definition: NodeMasks.h:1168
bool test() const
Definition: NodeMasks.h:194
void printBits(std::ostream &os=std::cout, Index32 max_out=80u) const
Definition: NodeMasks.h:1384
void increment()
Definition: NodeMasks.h:245
void setOff()
Definition: NodeMasks.h:1317
~RootNodeMask()
Definition: NodeMasks.h:1086
NodeMask operator^(const NodeMask &other) const
Definition: NodeMasks.h:435
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128