CFugue
bitcache.h
1 #ifndef __bitcache_h_11A6BC64_8CC3_447B_AD83_56BCF4FF0083__
2 #define __bitcache_h_11A6BC64_8CC3_447B_AD83_56BCF4FF0083__
3 
4 #include <vector>
5 #include <memory>
6 
7 #ifndef _ASSERTE
8 #define _ASSERTE(x) (0)
9 #endif
10 
11 #if !defined(_NO_TRANSFORM_SEQUENCES) || (!_NO_TRANSFORM_SEQUENCES)
12 #define _USE_TRANSFORM_SEQUENCES 1
13 #else
14 #define _USE_TRANSFORM_SEQUENCES 0
15 #endif
16 
17 #if _USE_TRANSFORM_SEQUENCES
18 #include <boost/mpl/begin_end.hpp>
19 #include <boost/mpl/next_prior.hpp>
20 #endif
21 
22 //#warning "INFO: some message for GCC Compilation"
23 namespace bc
24 {
25  typedef unsigned char BYTE;
26  typedef unsigned long long bitunit;
27  typedef std::vector<bitunit> ADVEC;
28 
29  typedef std::vector<bitunit> SetBitVec;
30 
31  template<typename T> struct LoadValVec { typedef std::vector<T> type; };
32  template<typename T> struct LoadValMap { typedef typename LoadValVec<typename LoadValVec<T>::type >::type type; };
33 
34 
35  // Returns the 0-based position of the highest bit set. For example, HiBitPosition<64>==6 and HiBitPosition<63>==5;
36  template<unsigned int x>
37  struct HiBitPosition
38  {
39  static const unsigned int Pos = HiBitPosition<(x >> 1)>::Pos + 1;
40  };
41  template<>
42  struct HiBitPosition<1>
43  {
44  static const unsigned int Pos = 0;
45  };
46 
47  // Creates a bitunit with all the bits in it set to 1
48  template<unsigned int x>
49  struct TurnOnAllBits
50  {
51  static const bitunit Value = (TurnOnAllBits<(x-1)>::Value | ((bitunit)1 << (x-1)));
52  };
53  template<>
54  struct TurnOnAllBits<1>
55  {
56  static const bitunit Value = (bitunit)1;
57  };
58 
59  struct mTraits
60  {
61  enum : size_t
62  {
63  nByteSizeInBits = sizeof(BYTE)*8,
64  nBytesPerBitUnit = sizeof(bitunit),
65  nBitsPerBitUnit = nBytesPerBitUnit * 8,
66  nBitUnitModuloMask = nBitsPerBitUnit - 1, // useful for computing the relative offset within a bitunit from the overall index
67  nBitUnitDivShiftBits= HiBitPosition<nBitsPerBitUnit>::Pos, // useful for dividing the overall index for arriving at bitunit index
68  };
69  enum : bitunit
70  {
71  nBitUnitAllBitsOn = TurnOnAllBits<nBitsPerBitUnit>::Value, // useful for setting and unsetting a range of bits
72  };
73  };
74 
75  template<unsigned int size> inline size_t _bitsum(const BYTE* pb) { _ASSERTE("Not Implemented: _bitsum(BYTE*)" == NULL); return -1; }
76 
77  template<typename T> inline size_t bitsum(T bu) { return _bitsum<sizeof(T)>((const BYTE*)&bu); }
78 
79  namespace Tr // Transform Methods
80  {
81  struct Null { template<typename T> inline static T tr(T b) { return b; } }; // Null Transform
82  struct Invert{ template<typename T> inline static T tr(T b) { return ~b; } }; // Inverts the given byte/int
83  struct And { template<typename T> inline static T tr(T a, T b) { return a & b; } }; // Boolean And
84  struct Or { template<typename T> inline static T tr(T a, T b) { return a | b; } }; // Boolean Or
85  }
86  namespace Pr // Predicate Methods
87  {
88  struct Equal { template<typename T1, typename T2> inline static bool pr(T1 t1, T2 t2) { return t1 == t2; } };
89  struct Less { template<typename T1, typename T2> inline static bool pr(T1 t1, T2 t2) { return t1 < t2; } };
90  struct Great { template<typename T1, typename T2> inline static bool pr(T1 t1, T2 t2) { return t1 > t2; } };
91  }
92  namespace Red // Reduction Methods
93  {
94  struct toBitCount { template<typename T> inline static size_t red(size_t res, T bu) { return res + bitsum(bu); } };
95  struct toMinVal { template<typename T> inline static T red(T res, T bu) { return bu < res ? bu : res; } };
96  struct toMaxVal { template<typename T> inline static T red(T res, T bu) { return bu > res ? bu : res; } };
97  struct toSum { template<typename T> inline static T red(T res, T val){ return res + val; } };
98  }
99 
100 #if _USE_TRANSFORM_SEQUENCES ///// Executes a transformation sequence over the given data ///////
101  namespace _detail
102  {
103  template<typename _tBegin, typename _tEnd>
104  struct _s
105  {
106  template<typename outType, typename inType>
107  static inline outType _apply(inType data) { return _s< typename boost::mpl::next< _tBegin >::type, _tEnd>::template _apply<outType>( _tBegin::type::tr(data) ); }
108 
109  template<typename outType, typename inType1, typename inType2>
110  static inline outType _apply(inType1 in1, inType2 in2) { return _s< typename boost::mpl::next< _tBegin >::type, _tEnd>::template _apply<outType>( _tBegin::type::tr(in1, in2) ); }
111  };
112 
113  template<typename _tEnd>
114  struct _s<_tEnd, _tEnd>
115  {
116  template<typename outType, typename inType>
117  static inline outType _apply(inType data) { return data; }
118  };
119 
120  template<typename TrSeq, typename outType, typename inType>
121  inline outType _exec(inType data) { return _s< typename boost::mpl::begin< TrSeq >::type, typename boost::mpl::end< TrSeq >::type>::template _apply<outType>(data); }
122 
123  template<typename TrSeq, typename outType, typename inType1, typename inType2>
124  inline outType _exec(inType1 in1, inType2 in2) { return _s< typename boost::mpl::begin< TrSeq >::type, typename boost::mpl::end< TrSeq >::type>::template _apply<outType>(in1, in2); }
125 
126  struct _unspecified_type { }; // useful as default type
127 
128  // type selection based on condition
129  template<typename T> struct isTypeSpecified { enum { Result = true }; };
130  template<> struct isTypeSpecified<_unspecified_type> { enum { Result = false }; };
131 
132  template<typename T1, typename T2> struct areTypesSame { enum { Result = false }; };
133  template<typename T> struct areTypesSame<T, T> { enum { Result = true }; };
134 
135  template<typename yesType, typename noType, bool cond=true> struct select { typedef yesType ResultType; };
136  template<typename yesType, typename noType> struct select<yesType, noType, false> { typedef noType ResultType; };
137  template<typename outType, typename inType>
138  struct selectValidType
139  {
140  typedef typename select<outType, inType, isTypeSpecified<outType>::Result >::ResultType ResultType; // if outType is unspecified, set the inType as outType
141  };
142  template<typename outType, typename inType1, typename inType2>
143  struct selectValidType2
144  {
145  typedef typename select<outType,
146  typename select<inType1, _unspecified_type, areTypesSame<inType1, inType2>::Result >::ResultType,
147  isTypeSpecified<outType>::Result
148  >::ResultType ResultType; // if outType is unspecified, set the inType1 as outType only if inType1 == inType2; otherwise leave it as unspecified
149  };
150  }
151  namespace Tr // Transform Sequence
152  {
153  template<typename Seq, typename outType = _detail::_unspecified_type> struct TrSeq
154  {
155  template<typename inType>
156  inline static typename _detail::selectValidType<outType, inType>::ResultType tr(inType b) { return _detail::_exec<Seq, typename _detail::selectValidType<outType, inType>::ResultType>(b); }
157 
158  template<typename inType1, typename inType2>
159  inline static typename _detail::selectValidType2<outType, inType1, inType2>::ResultType tr(inType1 in1, inType2 in2) { return _detail::_exec<Seq, typename _detail::selectValidType2<outType, inType1, inType2>::ResultType>(in1, in2); }
160  };
161  }
162  //// Transformation Sequence Usage Example:
163  //
164  // #include <boost/mpl/vector.hpp>
165  //
166  // std::vector<unsigned char> in(256);
167  // std::vector<size_t> out(256);
168  //
169  // bc::gen_seq(in, 0); //<-- generate the sequence data
170  //
171  // typedef boost::mpl::vector2<bc::Tr::Invert, TrBitSum<size_t> > invertedBitSum; //<-- define the transform sequence
172  //
173  // transform<Tr::TrSeq<invertedBitSum, size_t> >(in, out); //<-- apply the sequence over the input
174  //
175 #endif // _USE_TRANSFORM_SEQUENCES
176 
177  template<typename _Tr, typename TOut, typename _TIn1, typename _TIn2>
178  struct TRVEC
179  {
180  size_t _size;
181  struct const_pointer
182  {
183  typename _TIn1::const_pointer ptr1;
184  typename _TIn2::const_pointer ptr2;
185  inline TOut operator*() { return _Tr::tr(*ptr1, *ptr2); }
186  inline const_pointer& operator++() { ++ptr1; ++ptr2; return *this; }
187  inline const_pointer operator++(int) { return const_pointer(ptr1++, ptr2++); } // postfix
188  inline const_pointer(const typename _TIn1::const_pointer &p1, const typename _TIn2::const_pointer &p2) : ptr1(p1), ptr2(p2) { }
189  } _start ;
190  public:
191  // typedef typename const_pointer const_pointer;
192 
193  inline const_pointer data() const { return _start; }
194 
195  inline TRVEC(const _TIn1& in1, const _TIn1& in2) : _start(in1.data(), in2.data()), _size(in1.size()) { }
196 
197  inline size_t size() const { return _size; }
198  };
199  template<typename _Tr, typename TOut, typename TIn1, typename TIn2>
200  inline TRVEC<_Tr, TOut, TIn1, TIn2> trvec(const TIn1& in1, const TIn2& in2) { return TRVEC<_Tr, TOut, TIn1, TIn2>(in1, in2); }
201 
202  ////////////// Transform Methods //////////
203 
204  template<class _Transform, typename _VecIn, typename _VecOut>
205  inline void transform(const _VecIn& in, _VecOut& out) // copies transformed content to out
206  {
207  _ASSERTE(in.size() <= out.size());
208 
209  typename _VecOut::pointer pbOut = out.data();
210  typename _VecIn::const_pointer pbIn = in.data();
211  typename _VecIn::const_pointer const pbInLast = pbIn + in.size();
212 
213  while(pbIn != pbInLast)
214  {
215  *pbOut++ = _Transform::tr(*pbIn++);
216  }
217  }
218 
219  template<class _Transform, typename _vecIn1, typename _vecIn2, typename _vecOut>
220  inline void transform(const _vecIn1& in1, const _vecIn2& in2, _vecOut& out)
221  {
222  _ASSERTE(in1.size() <= in2.size());
223  _ASSERTE(in1.size() <= out.size());
224 
225  typename _vecOut::pointer pbOut = out.data();
226  typename _vecIn1::const_pointer pbIn1 = in1.data();
227  typename _vecIn2::const_pointer pbIn2 = in2.data();
228  typename _vecIn1::const_pointer const pbIn1Last = pbIn1 + in1.size();
229 
230  while(pbIn1 != pbIn1Last)
231  {
232  *pbOut++ = _Transform::tr(*pbIn1++, *pbIn2++);
233  }
234  }
235 
236  template<class _Tr1, class _Tr2, class _BinTr, typename _vecT1, typename _vecT2, typename _vecOut>
237  inline void zip(const _vecT1& in1, const _vecT2& in2, _vecOut& out) // out = BinTr(Tr1(in1), Tr2(in2))
238  {
239  _ASSERTE(in1.size() == in2.size() == out.size());
240 
241  typename _vecOut::pointer pbOut = out.data();
242  typename _vecT1::const_pointer pbIn1 = in1.data();
243  typename _vecT2::const_pointer pbIn2 = in2.data();
244 
245  for(size_t i=0, nMax = in1.size(); i < nMax; ++i)
246  {
247  *pbOut++ = _BinTr::tr(_Tr1::tr(*pbIn1++), _Tr2::tr(*pbIn2++));
248  }
249  }
250 
251  template<class _Red, class _Tr, typename Result, typename _vecT>
252  inline Result reduce(const _vecT& in, const Result& init = 0)
253  {
254  Result res(init);
255  typename _vecT::const_pointer pbIn = in.data();
256  typename _vecT::const_pointer const pbInLast = pbIn + in.size();
257 
258  while(pbIn != pbInLast)
259  res = _Red::red(res, _Tr::tr(*pbIn++));
260  return res;
261  }
262 
263  template<class _Red, class _Tr1, class _Tr2, typename Result, typename _vecT1, typename _vecT2>
264  inline Result reduce(const _vecT1& vec1, const _vecT2& vec2, const Result& init=0)
265  {
266  _ASSERTE(vec1.size() == vec2.size());
267 
268  Result res(init);
269  typename _vecT1::const_pointer pbVec1 = vec1.data();
270  typename _vecT2::const_pointer pbVec2 = vec2.data();
271 
272  for(size_t i=0, nMax = vec1.size(); i < nMax; ++i)
273  res = _Red::red(res, _Tr1::tr(*pbVec1++), _Tr2::tr(*pbVec2++));
274  return res;
275  }
276 
277  template<class _Transform, class _Red, typename Result, typename _vecT1, typename _vecT2>
278  inline Result transform_reduce(const _vecT1& vec1, const _vecT2& vec2, const Result& init=0)
279  {
280  Result res(init);
281  typename _vecT1::const_pointer pbVec1 = vec1.data();
282  typename _vecT2::const_pointer pbVec2 = vec2.data();
283 
284  for(size_t i=0, nMax = vec1.size(); i < nMax; ++i)
285  res = _Red::red(res, _Transform::tr(*pbVec1++, *pbVec2++));
286  return res;
287  }
288 
289  template<class _Transform, class _Red, typename Result, typename _vecT1, typename _vecT2, typename _vecOut>
290  inline Result transform_reduce(const _vecT1& vec1, const _vecT2& vec2, _vecOut& vecOut, const Result& init=0) // also stores the output of transform apart from applying the reduction
291  {
292  Result res(init);
293  typename _vecT1::const_pointer pbVec1 = vec1.data();
294  typename _vecT2::const_pointer pbVec2 = vec2.data();
295  typename _vecOut::pointer pvecOut = vecOut.data();
296 
297  for(size_t i=0, nMax = vec1.size(); i < nMax; ++i)
298  res = _Red::red(res, *pvecOut++ = _Transform::tr(*pbVec1++, *pbVec2++));
299  return res;
300  }
301 
302  template<class _Tr1, class _Tr2, class _BinTr, class _Red, typename Result, typename _vecT1, typename _vecT2, typename _vecOut>
303  inline Result zip_reduce(const _vecT1& in1, const _vecT2& in2, _vecOut& out, const Result& init=0) // Result = Red(Result, BinTr(Tr1(in1), Tr2(in2)))
304  {
305  _ASSERTE(in1.size() == in2.size() == out.size());
306 
307  Result res(init);
308  typename _vecOut::pointer pbOut = out.data();
309  typename _vecT2::const_pointer pbIn1 = in1.data();
310  typename _vecT1::const_pointer pbIn2 = in2.data();
311 
312  for(size_t i=0, nMax = in1.size(); i < nMax; ++i)
313  res = _Red::red(res, *pbOut++ = _BinTr::tr(_Tr1::tr(*pbIn1++), _Tr2::tr(*pbIn2++)));
314  return res;
315  }
316 
317  template<class _Tr1, class _Tr2, class _Pred, typename _vecT1, typename _vecT2>
318  inline bool comp(const _vecT1& vec1, const _vecT2& vec2) // returns true if _Pred::pr(_Tr1(vec1), _Tr2(vec2)) is true for all
319  {
320  typename _vecT1::const_pointer pbVec1 = vec1.data();
321  typename _vecT2::const_pointer pbVec2 = vec2.data();
322  const size_t nMax = vec1.size();
323  volatile size_t i=0;
324  while(i < nMax && _Pred::pr(_Tr1::tr(*pbVec1++), _Tr2::tr(*pbVec2++))) ++i;
325  return i >= nMax;
326  }
327 
328  template<class _Tr1, class _Tr2, class _Pred, typename _vecT1, typename _vecT2, typename TOut>
329  inline bool comp_set(const _vecT1& vec1, const _vecT2& vec2, TOut& out) // returns true if _Pred::pr(_Tr1(vec1), _Tr2(vec2)) is true for all, with optional value set in out
330  {
331  typename _vecT1::const_pointer pbVec1 = vec1.data();
332  typename _vecT2::const_pointer pbVec2 = vec2.data();
333  const size_t nMax = vec1.size();
334  volatile size_t i=0;
335  while(i < nMax && _Pred::pr(_Tr1::tr(*pbVec1++), _Tr2::tr(*pbVec2++), out)) ++i;
336  return i >= nMax;
337  }
338 
339  template<typename vecT, typename Result, typename _FindFn>
340  inline bool scan(const vecT& in, Result& res, _FindFn _found) // scan the input array till the search condition is met. Returns false if search fails.
341  {
342  typename vecT::const_pointer pVec = in.data();
343  for(size_t i=0, nMax = in.size(); i < nMax; ++i)
344  {
345  if(_found(res = *pVec++)) { return true; }
346  }
347  return false;
348  }
349 
350  template<typename _Red, typename vecT, typename Result, typename _FindFn>
351  inline Result scan_reduce(const vecT& in, Result& res, _FindFn _found) // scan the input array till the search condition is met. Returns false if search fails.
352  {
353  typename vecT::const_pointer pVec = in.data();
354  for(size_t i=0, nMax = in.size(); i < nMax; ++i, ++pVec)
355  {
356  const typename vecT::value_type val = *pVec;
357  if(_found(val)) { return res; }
358  res = _Red::red(res, val);
359  }
360  return res;
361  }
362 
363  typedef signed char BITID;
364  inline const BITID* GetOnBitPositions(BYTE b)
365  {
366  static const BITID OnBitPositions[256][9] = {
367  {-1,-1,-1,-1,-1,-1,-1,-1,-1,}, // [0]
368  {0, -1,-1,-1,-1,-1,-1,-1,-1,}, // [1]
369  {1, -1,-1,-1,-1,-1,-1,-1,-1,}, // [2]
370  {0, 1, -1,-1,-1,-1,-1,-1,-1,}, // [3]
371  {2, -1,-1,-1,-1,-1,-1,-1,-1,}, // [4]
372  {0, 2, -1,-1,-1,-1,-1,-1,-1,}, // [5]
373  {1, 2, -1,-1,-1,-1,-1,-1,-1,}, // [6]
374  {0, 1, 2, -1,-1,-1,-1,-1,-1,}, // [7]
375  {3, -1,-1,-1,-1,-1,-1,-1,-1,}, // [8]
376  {0, 3, -1,-1,-1,-1,-1,-1,-1,}, // [9]
377  {1, 3, -1,-1,-1,-1,-1,-1,-1,}, // [10]
378  {0, 1, 3, -1,-1,-1,-1,-1,-1,}, // [11]
379  {2, 3, -1,-1,-1,-1,-1,-1,-1,}, // [12]
380  {0, 2, 3, -1,-1,-1,-1,-1,-1,}, // [13]
381  {1, 2, 3, -1,-1,-1,-1,-1,-1,}, // [14]
382  {0, 1, 2, 3, -1,-1,-1,-1,-1,}, // [15]
383  {4, -1,-1,-1,-1,-1,-1,-1,-1,}, // [16]
384  {0, 4, -1,-1,-1,-1,-1,-1,-1,}, // [17]
385  {1, 4, -1,-1,-1,-1,-1,-1,-1,}, // [18]
386  {0, 1, 4, -1,-1,-1,-1,-1,-1,}, // [19]
387  {2, 4, -1,-1,-1,-1,-1,-1,-1,}, // [20]
388  {0, 2, 4, -1,-1,-1,-1,-1,-1,}, // [21]
389  {1, 2, 4, -1,-1,-1,-1,-1,-1,}, // [22]
390  {0, 1, 2, 4, -1,-1,-1,-1,-1,}, // [23]
391  {3, 4, -1,-1,-1,-1,-1,-1,-1,}, // [24]
392  {0, 3, 4, -1,-1,-1,-1,-1,-1,}, // [25]
393  {1, 3, 4, -1,-1,-1,-1,-1,-1,}, // [26]
394  {0, 1, 3, 4, -1,-1,-1,-1,-1,}, // [27]
395  {2, 3, 4, -1,-1,-1,-1,-1,-1,}, // [28]
396  {0, 2, 3, 4, -1,-1,-1,-1,-1,}, // [29]
397  {1, 2, 3, 4, -1,-1,-1,-1,-1,}, // [30]
398  {0, 1, 2, 3, 4, -1,-1,-1,-1,}, // [31]
399  {5, -1,-1,-1,-1,-1,-1,-1,-1,}, // [32]
400  {0, 5, -1,-1,-1,-1,-1,-1,-1,}, // [33]
401  {1, 5, -1,-1,-1,-1,-1,-1,-1,}, // [34]
402  {0, 1, 5, -1,-1,-1,-1,-1,-1,}, // [35]
403  {2, 5, -1,-1,-1,-1,-1,-1,-1,}, // [36]
404  {0, 2, 5, -1,-1,-1,-1,-1,-1,}, // [37]
405  {1, 2, 5, -1,-1,-1,-1,-1,-1,}, // [38]
406  {0, 1, 2, 5, -1,-1,-1,-1,-1,}, // [39]
407  {3, 5, -1,-1,-1,-1,-1,-1,-1,}, // [40]
408  {0, 3, 5, -1,-1,-1,-1,-1,-1,}, // [41]
409  {1, 3, 5, -1,-1,-1,-1,-1,-1,}, // [42]
410  {0, 1, 3, 5, -1,-1,-1,-1,-1,}, // [43]
411  {2, 3, 5, -1,-1,-1,-1,-1,-1,}, // [44]
412  {0, 2, 3, 5, -1,-1,-1,-1,-1,}, // [45]
413  {1, 2, 3, 5, -1,-1,-1,-1,-1,}, // [46]
414  {0, 1, 2, 3, 5, -1,-1,-1,-1,}, // [47]
415  {4, 5, -1,-1,-1,-1,-1,-1,-1,}, // [48]
416  {0, 4, 5, -1,-1,-1,-1,-1,-1,}, // [49]
417  {1, 4, 5, -1,-1,-1,-1,-1,-1,}, // [50]
418  {0, 1, 4, 5, -1,-1,-1,-1,-1,}, // [51]
419  {2, 4, 5, -1,-1,-1,-1,-1,-1,}, // [52]
420  {0, 2, 4, 5, -1,-1,-1,-1,-1,}, // [53]
421  {1, 2, 4, 5, -1,-1,-1,-1,-1,}, // [54]
422  {0, 1, 2, 4, 5, -1,-1,-1,-1,}, // [55]
423  {3, 4, 5, -1,-1,-1,-1,-1,-1,}, // [56]
424  {0, 3, 4, 5, -1,-1,-1,-1,-1,}, // [57]
425  {1, 3, 4, 5, -1,-1,-1,-1,-1,}, // [58]
426  {0, 1, 3, 4, 5, -1,-1,-1,-1,}, // [59]
427  {2, 3, 4, 5, -1,-1,-1,-1,-1,}, // [60]
428  {0, 2, 3, 4, 5, -1,-1,-1,-1,}, // [61]
429  {1, 2, 3, 4, 5, -1,-1,-1,-1,}, // [62]
430  {0, 1, 2, 3, 4, 5, -1,-1,-1,}, // [63]
431  {6, -1,-1,-1,-1,-1,-1,-1,-1,}, // [64]
432  {0, 6, -1,-1,-1,-1,-1,-1,-1,}, // [65]
433  {1, 6, -1,-1,-1,-1,-1,-1,-1,}, // [66]
434  {0, 1, 6, -1,-1,-1,-1,-1,-1,}, // [67]
435  {2, 6, -1,-1,-1,-1,-1,-1,-1,}, // [68]
436  {0, 2, 6, -1,-1,-1,-1,-1,-1,}, // [69]
437  {1, 2, 6, -1,-1,-1,-1,-1,-1,}, // [70]
438  {0, 1, 2, 6, -1,-1,-1,-1,-1,}, // [71]
439  {3, 6, -1,-1,-1,-1,-1,-1,-1,}, // [72]
440  {0, 3, 6, -1,-1,-1,-1,-1,-1,}, // [73]
441  {1, 3, 6, -1,-1,-1,-1,-1,-1,}, // [74]
442  {0, 1, 3, 6, -1,-1,-1,-1,-1,}, // [75]
443  {2, 3, 6, -1,-1,-1,-1,-1,-1,}, // [76]
444  {0, 2, 3, 6, -1,-1,-1,-1,-1,}, // [77]
445  {1, 2, 3, 6, -1,-1,-1,-1,-1,}, // [78]
446  {0, 1, 2, 3, 6, -1,-1,-1,-1,}, // [79]
447  {4, 6, -1,-1,-1,-1,-1,-1,-1,}, // [80]
448  {0, 4, 6, -1,-1,-1,-1,-1,-1,}, // [81]
449  {1, 4, 6, -1,-1,-1,-1,-1,-1,}, // [82]
450  {0, 1, 4, 6, -1,-1,-1,-1,-1,}, // [83]
451  {2, 4, 6, -1,-1,-1,-1,-1,-1,}, // [84]
452  {0, 2, 4, 6, -1,-1,-1,-1,-1,}, // [85]
453  {1, 2, 4, 6, -1,-1,-1,-1,-1,}, // [86]
454  {0, 1, 2, 4, 6, -1,-1,-1,-1,}, // [87]
455  {3, 4, 6, -1,-1,-1,-1,-1,-1,}, // [88]
456  {0, 3, 4, 6, -1,-1,-1,-1,-1,}, // [89]
457  {1, 3, 4, 6, -1,-1,-1,-1,-1,}, // [90]
458  {0, 1, 3, 4, 6, -1,-1,-1,-1,}, // [91]
459  {2, 3, 4, 6, -1,-1,-1,-1,-1,}, // [92]
460  {0, 2, 3, 4, 6, -1,-1,-1,-1,}, // [93]
461  {1, 2, 3, 4, 6, -1,-1,-1,-1,}, // [94]
462  {0, 1, 2, 3, 4, 6, -1,-1,-1,}, // [95]
463  {5, 6, -1,-1,-1,-1,-1,-1,-1,}, // [96]
464  {0, 5, 6, -1,-1,-1,-1,-1,-1,}, // [97]
465  {1, 5, 6, -1,-1,-1,-1,-1,-1,}, // [98]
466  {0, 1, 5, 6, -1,-1,-1,-1,-1,}, // [99]
467  {2, 5, 6, -1,-1,-1,-1,-1,-1,}, // [100]
468  {0, 2, 5, 6, -1,-1,-1,-1,-1,}, // [101]
469  {1, 2, 5, 6, -1,-1,-1,-1,-1,}, // [102]
470  {0, 1, 2, 5, 6, -1,-1,-1,-1,}, // [103]
471  {3, 5, 6, -1,-1,-1,-1,-1,-1,}, // [104]
472  {0, 3, 5, 6, -1,-1,-1,-1,-1,}, // [105]
473  {1, 3, 5, 6, -1,-1,-1,-1,-1,}, // [106]
474  {0, 1, 3, 5, 6, -1,-1,-1,-1,}, // [107]
475  {2, 3, 5, 6, -1,-1,-1,-1,-1,}, // [108]
476  {0, 2, 3, 5, 6, -1,-1,-1,-1,}, // [109]
477  {1, 2, 3, 5, 6, -1,-1,-1,-1,}, // [110]
478  {0, 1, 2, 3, 5, 6, -1,-1,-1,}, // [111]
479  {4, 5, 6, -1,-1,-1,-1,-1,-1,}, // [112]
480  {0, 4, 5, 6, -1,-1,-1,-1,-1,}, // [113]
481  {1, 4, 5, 6, -1,-1,-1,-1,-1,}, // [114]
482  {0, 1, 4, 5, 6, -1,-1,-1,-1,}, // [115]
483  {2, 4, 5, 6, -1,-1,-1,-1,-1,}, // [116]
484  {0, 2, 4, 5, 6, -1,-1,-1,-1,}, // [117]
485  {1, 2, 4, 5, 6, -1,-1,-1,-1,}, // [118]
486  {0, 1, 2, 4, 5, 6, -1,-1,-1,}, // [119]
487  {3, 4, 5, 6, -1,-1,-1,-1,-1,}, // [120]
488  {0, 3, 4, 5, 6, -1,-1,-1,-1,}, // [121]
489  {1, 3, 4, 5, 6, -1,-1,-1,-1,}, // [122]
490  {0, 1, 3, 4, 5, 6, -1,-1,-1,}, // [123]
491  {2, 3, 4, 5, 6, -1,-1,-1,-1,}, // [124]
492  {0, 2, 3, 4, 5, 6, -1,-1,-1,}, // [125]
493  {1, 2, 3, 4, 5, 6, -1,-1,-1,}, // [126]
494  {0, 1, 2, 3, 4, 5, 6, -1,-1,}, // [127]
495  {7, -1,-1,-1,-1,-1,-1,-1,-1,}, // [128]
496  {0, 7, -1,-1,-1,-1,-1,-1,-1,}, // [129]
497  {1, 7, -1,-1,-1,-1,-1,-1,-1,}, // [130]
498  {0, 1, 7, -1,-1,-1,-1,-1,-1,}, // [131]
499  {2, 7, -1,-1,-1,-1,-1,-1,-1,}, // [132]
500  {0, 2, 7, -1,-1,-1,-1,-1,-1,}, // [133]
501  {1, 2, 7, -1,-1,-1,-1,-1,-1,}, // [134]
502  {0, 1, 2, 7, -1,-1,-1,-1,-1,}, // [135]
503  {3, 7, -1,-1,-1,-1,-1,-1,-1,}, // [136]
504  {0, 3, 7, -1,-1,-1,-1,-1,-1,}, // [137]
505  {1, 3, 7, -1,-1,-1,-1,-1,-1,}, // [138]
506  {0, 1, 3, 7, -1,-1,-1,-1,-1,}, // [139]
507  {2, 3, 7, -1,-1,-1,-1,-1,-1,}, // [140]
508  {0, 2, 3, 7, -1,-1,-1,-1,-1,}, // [141]
509  {1, 2, 3, 7, -1,-1,-1,-1,-1,}, // [142]
510  {0, 1, 2, 3, 7, -1,-1,-1,-1,}, // [143]
511  {4, 7, -1,-1,-1,-1,-1,-1,-1,}, // [144]
512  {0, 4, 7, -1,-1,-1,-1,-1,-1,}, // [145]
513  {1, 4, 7, -1,-1,-1,-1,-1,-1,}, // [146]
514  {0, 1, 4, 7, -1,-1,-1,-1,-1,}, // [147]
515  {2, 4, 7, -1,-1,-1,-1,-1,-1,}, // [148]
516  {0, 2, 4, 7, -1,-1,-1,-1,-1,}, // [149]
517  {1, 2, 4, 7, -1,-1,-1,-1,-1,}, // [150]
518  {0, 1, 2, 4, 7, -1,-1,-1,-1,}, // [151]
519  {3, 4, 7, -1,-1,-1,-1,-1,-1,}, // [152]
520  {0, 3, 4, 7, -1,-1,-1,-1,-1,}, // [153]
521  {1, 3, 4, 7, -1,-1,-1,-1,-1,}, // [154]
522  {0, 1, 3, 4, 7, -1,-1,-1,-1,}, // [155]
523  {2, 3, 4, 7, -1,-1,-1,-1,-1,}, // [156]
524  {0, 2, 3, 4, 7, -1,-1,-1,-1,}, // [157]
525  {1, 2, 3, 4, 7, -1,-1,-1,-1,}, // [158]
526  {0, 1, 2, 3, 4, 7, -1,-1,-1,}, // [159]
527  {5, 7, -1,-1,-1,-1,-1,-1,-1,}, // [160]
528  {0, 5, 7, -1,-1,-1,-1,-1,-1,}, // [161]
529  {1, 5, 7, -1,-1,-1,-1,-1,-1,}, // [162]
530  {0, 1, 5, 7, -1,-1,-1,-1,-1,}, // [163]
531  {2, 5, 7, -1,-1,-1,-1,-1,-1,}, // [164]
532  {0, 2, 5, 7, -1,-1,-1,-1,-1,}, // [165]
533  {1, 2, 5, 7, -1,-1,-1,-1,-1,}, // [166]
534  {0, 1, 2, 5, 7, -1,-1,-1,-1,}, // [167]
535  {3, 5, 7, -1,-1,-1,-1,-1,-1,}, // [168]
536  {0, 3, 5, 7, -1,-1,-1,-1,-1,}, // [169]
537  {1, 3, 5, 7, -1,-1,-1,-1,-1,}, // [170]
538  {0, 1, 3, 5, 7, -1,-1,-1,-1,}, // [171]
539  {2, 3, 5, 7, -1,-1,-1,-1,-1,}, // [172]
540  {0, 2, 3, 5, 7, -1,-1,-1,-1,}, // [173]
541  {1, 2, 3, 5, 7, -1,-1,-1,-1,}, // [174]
542  {0, 1, 2, 3, 5, 7, -1,-1,-1,}, // [175]
543  {4, 5, 7, -1,-1,-1,-1,-1,-1,}, // [176]
544  {0, 4, 5, 7, -1,-1,-1,-1,-1,}, // [177]
545  {1, 4, 5, 7, -1,-1,-1,-1,-1,}, // [178]
546  {0, 1, 4, 5, 7, -1,-1,-1,-1,}, // [179]
547  {2, 4, 5, 7, -1,-1,-1,-1,-1,}, // [180]
548  {0, 2, 4, 5, 7, -1,-1,-1,-1,}, // [181]
549  {1, 2, 4, 5, 7, -1,-1,-1,-1,}, // [182]
550  {0, 1, 2, 4, 5, 7, -1,-1,-1,}, // [183]
551  {3, 4, 5, 7, -1,-1,-1,-1,-1,}, // [184]
552  {0, 3, 4, 5, 7, -1,-1,-1,-1,}, // [185]
553  {1, 3, 4, 5, 7, -1,-1,-1,-1,}, // [186]
554  {0, 1, 3, 4, 5, 7, -1,-1,-1,}, // [187]
555  {2, 3, 4, 5, 7, -1,-1,-1,-1,}, // [188]
556  {0, 2, 3, 4, 5, 7, -1,-1,-1,}, // [189]
557  {1, 2, 3, 4, 5, 7, -1,-1,-1,}, // [190]
558  {0, 1, 2, 3, 4, 5, 7, -1,-1,}, // [191]
559  {6, 7, -1,-1,-1,-1,-1,-1,-1,}, // [192]
560  {0, 6, 7, -1,-1,-1,-1,-1,-1,}, // [193]
561  {1, 6, 7, -1,-1,-1,-1,-1,-1,}, // [194]
562  {0, 1, 6, 7, -1,-1,-1,-1,-1,}, // [195]
563  {2, 6, 7, -1,-1,-1,-1,-1,-1,}, // [196]
564  {0, 2, 6, 7, -1,-1,-1,-1,-1,}, // [197]
565  {1, 2, 6, 7, -1,-1,-1,-1,-1,}, // [198]
566  {0, 1, 2, 6, 7, -1,-1,-1,-1,}, // [199]
567  {3, 6, 7, -1,-1,-1,-1,-1,-1,}, // [200]
568  {0, 3, 6, 7, -1,-1,-1,-1,-1,}, // [201]
569  {1, 3, 6, 7, -1,-1,-1,-1,-1,}, // [202]
570  {0, 1, 3, 6, 7, -1,-1,-1,-1,}, // [203]
571  {2, 3, 6, 7, -1,-1,-1,-1,-1,}, // [204]
572  {0, 2, 3, 6, 7, -1,-1,-1,-1,}, // [205]
573  {1, 2, 3, 6, 7, -1,-1,-1,-1,}, // [206]
574  {0, 1, 2, 3, 6, 7, -1,-1,-1,}, // [207]
575  {4, 6, 7, -1,-1,-1,-1,-1,-1,}, // [208]
576  {0, 4, 6, 7, -1,-1,-1,-1,-1,}, // [209]
577  {1, 4, 6, 7, -1,-1,-1,-1,-1,}, // [210]
578  {0, 1, 4, 6, 7, -1,-1,-1,-1,}, // [211]
579  {2, 4, 6, 7, -1,-1,-1,-1,-1,}, // [212]
580  {0, 2, 4, 6, 7, -1,-1,-1,-1,}, // [213]
581  {1, 2, 4, 6, 7, -1,-1,-1,-1,}, // [214]
582  {0, 1, 2, 4, 6, 7, -1,-1,-1,}, // [215]
583  {3, 4, 6, 7, -1,-1,-1,-1,-1,}, // [216]
584  {0, 3, 4, 6, 7, -1,-1,-1,-1,}, // [217]
585  {1, 3, 4, 6, 7, -1,-1,-1,-1,}, // [218]
586  {0, 1, 3, 4, 6, 7, -1,-1,-1,}, // [219]
587  {2, 3, 4, 6, 7, -1,-1,-1,-1,}, // [220]
588  {0, 2, 3, 4, 6, 7, -1,-1,-1,}, // [221]
589  {1, 2, 3, 4, 6, 7, -1,-1,-1,}, // [222]
590  {0, 1, 2, 3, 4, 6, 7, -1,-1,}, // [223]
591  {5, 6, 7, -1,-1,-1,-1,-1,-1,}, // [224]
592  {0, 5, 6, 7, -1,-1,-1,-1,-1,}, // [225]
593  {1, 5, 6, 7, -1,-1,-1,-1,-1,}, // [226]
594  {0, 1, 5, 6, 7, -1,-1,-1,-1,}, // [227]
595  {2, 5, 6, 7, -1,-1,-1,-1,-1,}, // [228]
596  {0, 2, 5, 6, 7, -1,-1,-1,-1,}, // [229]
597  {1, 2, 5, 6, 7, -1,-1,-1,-1,}, // [230]
598  {0, 1, 2, 5, 6, 7, -1,-1,-1,}, // [231]
599  {3, 5, 6, 7, -1,-1,-1,-1,-1,}, // [232]
600  {0, 3, 5, 6, 7, -1,-1,-1,-1,}, // [233]
601  {1, 3, 5, 6, 7, -1,-1,-1,-1,}, // [234]
602  {0, 1, 3, 5, 6, 7, -1,-1,-1,}, // [235]
603  {2, 3, 5, 6, 7, -1,-1,-1,-1,}, // [236]
604  {0, 2, 3, 5, 6, 7, -1,-1,-1,}, // [237]
605  {1, 2, 3, 5, 6, 7, -1,-1,-1,}, // [238]
606  {0, 1, 2, 3, 5, 6, 7, -1,-1,}, // [239]
607  {4, 5, 6, 7, -1,-1,-1,-1,-1,}, // [240]
608  {0, 4, 5, 6, 7, -1,-1,-1,-1,}, // [241]
609  {1, 4, 5, 6, 7, -1,-1,-1,-1,}, // [242]
610  {0, 1, 4, 5, 6, 7, -1,-1,-1,}, // [243]
611  {2, 4, 5, 6, 7, -1,-1,-1,-1,}, // [244]
612  {0, 2, 4, 5, 6, 7, -1,-1,-1,}, // [245]
613  {1, 2, 4, 5, 6, 7, -1,-1,-1,}, // [246]
614  {0, 1, 2, 4, 5, 6, 7, -1,-1,}, // [247]
615  {3, 4, 5, 6, 7, -1,-1,-1,-1,}, // [248]
616  {0, 3, 4, 5, 6, 7, -1,-1,-1,}, // [249]
617  {1, 3, 4, 5, 6, 7, -1,-1,-1,}, // [250]
618  {0, 1, 3, 4, 5, 6, 7, -1,-1,}, // [251]
619  {2, 3, 4, 5, 6, 7, -1,-1,-1,}, // [252]
620  {0, 2, 3, 4, 5, 6, 7, -1,-1,}, // [253]
621  {1, 2, 3, 4, 5, 6, 7, -1,-1,}, // [254]
622  {0, 1, 2, 3, 4, 5, 6, 7, -1,}, // [255]
623  };
624  return OnBitPositions[b];
625  }
626 
627  template<class _Transform, class _Fn>
628  inline void for_each_bit_uncond(const ADVEC& advec, _Fn _op) // applies _Fn for each ON bit thats a result of _Transform
629  {
630  const bitunit* pBitUnit = &advec[0];
631  const BYTE* pByte = (BYTE*)pBitUnit;
632  for(size_t i=0, nBitOffset=0, nByteCount = mTraits::nBytesPerBitUnit * advec.size(); i < nByteCount; ++i, ++pByte, nBitOffset += mTraits::nByteSizeInBits)
633  {
634  const BITID* pBitID = GetOnBitPositions(_Transform::tr(*pByte));
635  while(*pBitID >= 0)
636  {
637  _op((size_t)*pBitID + nBitOffset);
638  ++pBitID;
639  }
640  }
641  }
642 
643  template<class _Transform, class _Fn>
644  inline void for_each_bit_uncond(const ADVEC& advec1, const ADVEC& advec2, _Fn _op) // applies _Fn for each ON bit thats a result of _Transform
645  {
646  _ASSERTE(advec1.size() <= advec2.size());
647  const bitunit* pBitUnit1 = &advec1[0]; const BYTE* pByte1 = (BYTE*)pBitUnit1;
648  const bitunit* pBitUnit2 = &advec2[0]; const BYTE* pByte2 = (BYTE*)pBitUnit2;
649  for(size_t i=0, nBitOffset=0, nByteCount = mTraits::nBytesPerBitUnit * advec1.size(); i < nByteCount; ++i, ++pByte1, ++pByte2, nBitOffset += mTraits::nByteSizeInBits)
650  {
651  const BITID* pBitID = GetOnBitPositions(_Transform::tr(*pByte1, *pByte2));
652  while(*pBitID >= 0)
653  {
654  _op((size_t)*pBitID + nBitOffset);
655  ++pBitID;
656  }
657  }
658  }
659 
660  template<class _Transform, class _Fn>
661  inline bool for_each_setbit_while(const ADVEC& advec, _Fn _op) // applies _Fn for each ON bit while the _op returns true;
662  {
663  const bitunit* pBitUnit = &advec[0];
664  const BYTE* pByte = (BYTE*)pBitUnit;
665  for(size_t i=0, nBitOffset=0, nByteCount = mTraits::nBytesPerBitUnit * advec.size(); i < nByteCount; ++i, ++pByte, nBitOffset += mTraits::nByteSizeInBits)
666  {
667  const BITID* pBitID = GetOnBitPositions(_Transform::tr(*pByte));
668  while(*pBitID >= 0)
669  {
670  if(_op((size_t)*pBitID + nBitOffset) == false) return false;
671  ++pBitID;
672  }
673  }
674  return true;
675  }
676 
677  template<typename vecType, class _Fn>
678  inline void for_each_unit(vecType& advec, _Fn _op)
679  {
680  typename vecType::value_type* pbu = &advec[0];
681  for(size_t i=0, nMax = advec.size(); i < nMax; ++i)
682  _op(*pbu++);
683  }
684 
685  template<typename _vecIn, typename _vecOut, class _Fn>
686  inline void for_each_unit_output(const _vecIn& in, _vecOut& out, _Fn _op)
687  {
688  typename _vecOut::value_type* pbuOut = &out[0];
689  const typename _vecIn::value_type* pbuIn = &in[0];
690  for(size_t i=0, nMax=in.size(); i < nMax; ++i)
691  *pbuOut++ = _op(*pbuIn++);
692  }
693 
694  template<typename TLoadValVec, class _Fn>
695  inline void for_each_pair(const TLoadValVec& vec, _Fn _op) // invoke _Fn on each pair of values in vec.
696  {
697  const typename TLoadValVec::value_type* pVali = &vec[0];
698  for(size_t i=0, nMax = vec.size(), iMax = nMax-1; i < iMax; ++i, ++pVali)
699  {
700  const typename TLoadValVec::value_type* pValj = pVali+1;
701  for(size_t j=i+1; j < nMax; ++j)
702  _op(*pVali, *pValj++);
703  }
704  }
705 
706  template<typename TLoadValVec, typename TLoadValMap, class _Fn>
707  inline void for_each_pair_output(const TLoadValVec& vecIn, TLoadValMap& mapOut ,_Fn _op) // invoke _Fn on each pair of values in vec. and output it to mapOut
708  {
709  const typename TLoadValVec::value_type* pVali = &vecIn[0];
710  for(size_t i=0, nMax = vecIn.size(), iMax = nMax-1; i < iMax; ++i, ++pVali)
711  {
712  typename TLoadValMap::value_type::value_type* pOut = &mapOut[i][i+1];
713  const typename TLoadValVec::value_type* pValj = pVali+1;
714  for(size_t j=i+1; j < nMax; ++j)
715  *pOut++ = _op(*pVali, *pValj++);
716  }
717  }
718 
719  template<typename TLoadValVec1, typename TLoadValVec2, class _Fn>
720  inline void for_each_pair(const TLoadValVec1& vec1, const TLoadValVec2& vec2, _Fn _op) // invoke _Fn for each pair of values from (vec1 x vec2)
721  {
722  const typename TLoadValVec1::value_type* pVal1 = &vec1[0];
723  for(size_t i=0, iMax = vec1.size(); i < iMax; ++i, ++pVal1)
724  {
725  const typename TLoadValVec2::value_type* pVal2 = &vec2[0];
726  for(size_t j=0, jMax = vec2.size(); j < jMax; ++j)
727  _op(*pVal1, *pVal2++);
728  }
729  }
730 
731  ///////////////////// utility wrappers //////////////////////////
732  template<typename _vecIn, typename _vecOut>
733  inline void make_copy(const _vecIn& in, _vecOut& out) // copies as-is.
734  {
735  transform<Tr::Null>(in, out);
736  }
737 
738  template<typename _vecIn, typename _vecOut>
739  inline void make_inverted_copy(const _vecIn& in, _vecOut& out) // copies inverted content to out
740  {
741  transform<Tr::Invert>(in, out);
742  }
743 
744  template<typename _vecT>
745  inline void invert(_vecT& in) // inverts the content in-place
746  {
747  make_inverted_copy(in, in);
748  }
749 
750  template<typename _vecT1, typename _vecT2>
751  bool is_equal(const _vecT1& vec1, const _vecT2& vec2)
752  {
753  return comp<Tr::Null, Tr::Null, Pr::Equal>(vec1, vec2);
754  }
755 
756  template<class _Fn, typename _vecT>
757  inline void for_each_setbit(const _vecT& advec, _Fn _op)
758  {
759  for_each_bit_uncond<Tr::Null>(advec, _op);
760  }
761 
762  template<class _Fn, typename _vecT>
763  inline void for_each_unsetbit(const _vecT& advec, _Fn _op)
764  {
765  for_each_bit_uncond<Tr::Invert>(advec, _op);
766  }
767 
768  // Sets the bit to true at the given 0-based nBitPos index in the advec
769  inline void setbit(ADVEC& advec, size_t nBitPos)
770  {
771  const size_t nBitUnitIndex = nBitPos >> mTraits::nBitUnitDivShiftBits; // nBitUnitIndex = nBitPos/nBitsPerBitUnit;
772  const size_t nBitOffset = nBitPos & mTraits::nBitUnitModuloMask; // nBitOffset = nBitPos % nBitsPerBitUnit;
773 
774  _ASSERTE((nBitPos % mTraits::nBitsPerBitUnit) == nBitOffset);
775  _ASSERTE((nBitPos / mTraits::nBitsPerBitUnit) == nBitUnitIndex);
776 
777  advec[nBitUnitIndex] |= ((bitunit)1 << nBitOffset);
778  }
779 
780  // Sets the bit to false at the given 0-based nBitPos index in the advec
781  inline void unsetbit(ADVEC& advec, size_t nBitPos)
782  {
783  const size_t nBitUnitIndex = nBitPos >> mTraits::nBitUnitDivShiftBits; // nBitUnitIndex = nBitPos/nBitsPerBitUnit;
784  const size_t nBitOffset = nBitPos & mTraits::nBitUnitModuloMask; // nBitOffset = nBitPos % nBitsPerBitUnit;
785 
786  _ASSERTE((nBitPos % mTraits::nBitsPerBitUnit) == nBitOffset);
787  _ASSERTE((nBitPos / mTraits::nBitsPerBitUnit) == nBitUnitIndex);
788 
789  advec[nBitUnitIndex] &= ~((bitunit)1 << nBitOffset);
790  }
791 
792  inline void setbits(ADVEC& advec, size_t nBitPosStart, size_t nBitPosEnd) // Sets all bits in the range [nBitPosStart, nBitPosEnd] to 1
793  {
794  const size_t nBitUnitIndexEnd = nBitPosEnd >> mTraits::nBitUnitDivShiftBits;
795  const size_t nBitOffsetEnd = nBitPosEnd & mTraits::nBitUnitModuloMask;
796  const size_t nBitOffset = nBitPosStart & mTraits::nBitUnitModuloMask;
797  size_t nBitUnitIndex = nBitPosStart >> mTraits::nBitUnitDivShiftBits;
798 
799  if(nBitUnitIndex == nBitUnitIndexEnd)
800  {
801  advec[nBitUnitIndex] |= (((bitunit)mTraits::nBitUnitAllBitsOn << nBitOffset) & ((bitunit)mTraits::nBitUnitAllBitsOn >> (bitunit)(mTraits::nBitsPerBitUnit-(nBitOffsetEnd+1))));
802  return;
803  }
804 
805  advec[nBitUnitIndex] |= ((bitunit)mTraits::nBitUnitAllBitsOn << nBitOffset);
806 
807  while(++nBitUnitIndex < nBitUnitIndexEnd)
808  advec[nBitUnitIndex] |= ((bitunit)mTraits::nBitUnitAllBitsOn);
809 
810  advec[nBitUnitIndex] |= ((bitunit)mTraits::nBitUnitAllBitsOn >> (bitunit)(mTraits::nBitsPerBitUnit-(nBitOffsetEnd+1)));
811  }
812 
813  inline void unsetbits(ADVEC& advec, size_t nBitPosStart, size_t nBitPosEnd) // Sets all bits in the range [nBitPosStart, nBitPosEnd] to 0
814  {
815  const size_t nBitUnitIndexEnd = nBitPosEnd >> mTraits::nBitUnitDivShiftBits;
816  const size_t nBitOffsetEnd = nBitPosEnd & mTraits::nBitUnitModuloMask;
817  const size_t nBitOffset = nBitPosStart & mTraits::nBitUnitModuloMask;
818  size_t nBitUnitIndex = nBitPosStart >> mTraits::nBitUnitDivShiftBits;
819 
820  if(nBitUnitIndex == nBitUnitIndexEnd)
821  {
822  advec[nBitUnitIndex] &= ~(((bitunit)mTraits::nBitUnitAllBitsOn << nBitOffset) & ((bitunit)mTraits::nBitUnitAllBitsOn >> (bitunit)(mTraits::nBitsPerBitUnit-(nBitOffsetEnd+1))));
823  return;
824  }
825 
826  advec[nBitUnitIndex] &= ~((bitunit)mTraits::nBitUnitAllBitsOn << nBitOffset);
827 
828  while(++nBitUnitIndex < nBitUnitIndexEnd)
829  advec[nBitUnitIndex] &= ~((bitunit)mTraits::nBitUnitAllBitsOn);
830 
831  advec[nBitUnitIndex] &= ~((bitunit)mTraits::nBitUnitAllBitsOn >> (bitunit)(mTraits::nBitsPerBitUnit-(nBitOffsetEnd+1)));
832  }
833 
834  inline void unsetbits(ADVEC& advec, size_t nBitPosStart) // Sets all bits in the advec to 0 starting from position nBitPosStart
835  {
836  unsetbits(advec, nBitPosStart, (advec.size() * mTraits::nBitsPerBitUnit) - 1);
837  }
838 
839  inline void setallbits(ADVEC& advec)
840  {
841  bitunit* pbu = &advec[0];
842  const bitunit* const pbuLast = pbu + advec.size();
843  while(pbu != pbuLast) *pbu++ = (bitunit) mTraits::nBitUnitAllBitsOn;
844  }
845 
846  inline void unsetallbits(ADVEC& advec)
847  {
848  bitunit* pbu = &advec[0];
849  const bitunit* const pbuLast = pbu + advec.size();
850  while(pbu != pbuLast) *pbu++ = (bitunit) 0;
851  }
852 
853  inline bool isbitset(const ADVEC& advec, size_t nBitPos)
854  {
855  const size_t nBitUnitIndex = nBitPos >> mTraits::nBitUnitDivShiftBits; // nBitUnitIndex = nBitPos/nBitsPerBitUnit;
856  const size_t nBitOffset = nBitPos & mTraits::nBitUnitModuloMask; // nBitOffset = nBitPos % nBitsPerBitUnit;
857 
858  _ASSERTE((nBitPos % mTraits::nBitsPerBitUnit) == nBitOffset);
859  _ASSERTE((nBitPos / mTraits::nBitsPerBitUnit) == nBitUnitIndex);
860 
861  return (advec[nBitUnitIndex] & ((bitunit)1 << nBitOffset)) != 0 ;
862  }
863 
864  inline size_t getfirstsetbit(const ADVEC& advec)
865  {
866  const bitunit* pBitUnit = &advec[0];
867 
868  size_t nBitOffset=0, byteIndex =0;
869 
870  while(*pBitUnit == 0)
871  {
872  ++pBitUnit, nBitOffset += mTraits::nBitsPerBitUnit;
873 #if _DEBUG
874  _ASSERTE(byteIndex < mTraits::nBytesPerBitUnit * advec.size()); // if this assertion has hit, then the input vector has no set bits !! Its empty
875  byteIndex += mTraits::nBytesPerBitUnit;
876 #endif
877  }
878 
879  const BYTE* pByte = (BYTE*)pBitUnit;
880  while(*pByte == 0) { ++pByte; nBitOffset += mTraits::nByteSizeInBits; }
881 
882  const BITID* pBitID = GetOnBitPositions(*pByte); _ASSERTE(isbitset(advec, *pBitID + nBitOffset) == true);
883  return *pBitID + nBitOffset;
884  }
885 
886  /////////// bit count utilities /////////////////////
887 
888  inline size_t bitsum(BYTE b) { static const char *const _Bitsperbyte =
889  "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"
890  "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
891  "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
892  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
893  "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
894  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
895  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
896  "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
897  "\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
898  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
899  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
900  "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
901  "\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
902  "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
903  "\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
904  "\4\5\5\6\5\6\6\7\5\6\6\7\6\7\7\x8"; return _Bitsperbyte[b]; }
905  template<>
906  inline size_t _bitsum<1>(const BYTE* pb) { return bitsum(pb[0]); }
907  template<>
908  inline size_t _bitsum<2>(const BYTE* pb) { return bitsum(pb[0]) + bitsum(pb[1]); }
909  template<>
910  inline size_t _bitsum<4>(const BYTE* pb) { return bitsum(pb[0]) + bitsum(pb[1]) + bitsum(pb[2]) + bitsum(pb[3]); }
911  template<>
912  inline size_t _bitsum<8>(const BYTE* pb) { return bitsum(pb[0]) + bitsum(pb[1]) + bitsum(pb[2]) + bitsum(pb[3]) + bitsum(pb[4]) + bitsum(pb[5]) + bitsum(pb[6]) + bitsum(pb[7]); }
913  template<>
914  inline size_t _bitsum<16>(const BYTE* pb){ return bitsum(pb[0]) + bitsum(pb[1]) + bitsum(pb[2]) + bitsum(pb[3]) + bitsum(pb[4]) + bitsum(pb[5]) + bitsum(pb[6]) + bitsum(pb[7]) + bitsum(pb[8]) + bitsum(pb[9]) + bitsum(pb[10]) + bitsum(pb[11]) + bitsum(pb[12]) + bitsum(pb[13]) + bitsum(pb[14]) + bitsum(pb[15]); }
915 
916  template<typename T>
917  inline size_t bitsum(const std::vector<T>& advec)
918  {
919  return reduce<Red::toBitCount, Tr::Null> (advec, (size_t)0);
920  }
921 
922  //////////// Sequence generator utilities //////////////////////
923 
924  template<typename T>
925  inline ADVEC gen_seq(T first, T end) // generates sequence of values in the range [first, end)
926  {
927  ADVEC seq(end - first);
928  bitunit* pbu = &seq[0];
929  while(first < end)
930  *pbu++ = first ++;
931  return seq;
932  }
933  template<typename _vecType, typename T>
934  inline void gen_seq(_vecType& vec, T first, T step=1) // generates sequence of values in the range [first, end)
935  {
936  typename _vecType::iterator iter = vec.begin();
937  typename _vecType::iterator iterEnd = vec.end();
938  for(; iter != iterEnd; ++iter, first += step)
939  {
940  *iter = first;
941  }
942  }
943 
944  ////////////// Debug Helpers /////////////////////////////////////
945 #if _DEBUG
946 #include <string>
947 #include <stdlib.h>
948  inline std::string toString(const SetBitVec& vec)
949  {
950  char numBuf[mTraits::nBitsPerBitUnit+1];
951  std::string str("{");
952  for_each_setbit(vec, [&](size_t id) { sprintf(numBuf, "%llu,", (uintptr_t)id); str += numBuf; } );
953  str += "}";
954  return str;
955  }
956  template<typename T>
957  inline std::string toString(const T& obj)
958  {
959  char numBuf[mTraits::nBitsPerBitUnit+1];
960  std::string str("{");
961  std::for_each(obj.cbegin(), obj.cend(), [&](T::value_type val) { sprintf(numBuf, "%llu,", (uintptr_t)val); str += numBuf; });
962  str += "}";
963  return str;
964  }
965 #endif
966 
967 } // namespace bc
968 
969 /////////////////////////////////////////////////////////////
970 //
971 /** -------- OnBitPositions Generator code -------------
972  **
973  void PrintOnBits(unsigned char ch)
974  {
975  printf("{");
976  int nSetCount=0;
977  for(int i=0; i < 8; ++i, ch = (ch >> 1))
978  if(ch & 1) { printf("%d, ", i); nSetCount++; }
979  while(nSetCount++ < 9) printf("-1,");
980  printf("}");
981  }
982  main()
983  {
984  printf("int OnBits[256][9] = {\n\t\t");
985  for(int i=0; i < 256; ++i)
986  {
987  PrintOnBits((unsigned char)i); printf(", \t // [%d] \n \t\t",i);
988  }
989  printf("};");
990  }
991  **
992  **/
993 /////////////////////////////////////////////////////////////
994 
995 #endif // __bitcache_h_11A6BC64_8CC3_447B_AD83_56BCF4FF0083__
bc::_detail::isTypeSpecified
Definition: bitcache.h:129
bc::_detail::_s
Definition: bitcache.h:104
bc::_detail::areTypesSame
Definition: bitcache.h:132
bc::_detail::selectValidType
Definition: bitcache.h:138
bc::_detail::select
Definition: bitcache.h:135
bc::TRVEC::const_pointer
Definition: bitcache.h:181
bc::_detail::_unspecified_type
Definition: bitcache.h:126
bc::_detail::selectValidType2
Definition: bitcache.h:143
CFugue, the C++ Music Programming Library © Copyright 2009 Cenacle Research India Private Limited Gopalakrishna Palem