diff options
Diffstat (limited to 'chilbert/GrayCodeRank.hpp')
| -rw-r--r-- | chilbert/GrayCodeRank.hpp | 293 |
1 files changed, 142 insertions, 151 deletions
diff --git a/chilbert/GrayCodeRank.hpp b/chilbert/GrayCodeRank.hpp index cff8dfc..3083489 100644 --- a/chilbert/GrayCodeRank.hpp +++ b/chilbert/GrayCodeRank.hpp @@ -19,179 +19,170 @@ #ifndef CHILBERT_GRAYCODERANK_HPP #define CHILBERT_GRAYCODERANK_HPP - -#include "chilbert/FixBitVec.hpp" #include "chilbert/BigBitVec.hpp" +#include "chilbert/FixBitVec.hpp" #include <cassert> -namespace chilbert +namespace chilbert { + +// This is the bulk of the cost in calculating +// a Compact Hilbert Index. It compresses a previously +// calculated index when provided the rotation +// at each level of precision. +template <class H, class HC> +inline void +compactIndex(const int* ms, const int* ds, int n, int m, H& h, HC& hc) { - // This is the bulk of the cost in calculating - // a Compact Hilbert Index. It compresses a previously - // calculated index when provided the rotation - // at each level of precision. - template<class H,class HC> - inline - void - compactIndex( - const int *ms, - const int *ds, - int n, - int m, - H &h, - HC &hc - ) - { - hc = 0; - - int hi = 0; - int hci = 0; - - // Run through the levels of precision - for ( int i = 0; i < m; i++ ) - { - // Run through the dimensions - int j = ds[i]; - do - { - // This dimension contributes a bit? - if ( ms[j] > i ) - { - if (testBit(h, hi)) { - setBit(hc, hci); - } - ++hci; + hc = 0; + + int hi = 0; + int hci = 0; + + // Run through the levels of precision + for (int i = 0; i < m; i++) { + // Run through the dimensions + int j = ds[i]; + do { + // This dimension contributes a bit? + if (ms[j] > i) { + if (testBit(h, hi)) { + setBit(hc, hci); } + ++hci; + } - if ( ++j == n ) j = 0; - ++hi; + if (++j == n) { + j = 0; } - while ( j != ds[i] ); - } + ++hi; + } while (j != ds[i]); } +} - template<class I> - inline - void - grayCodeRank( - const I &mask, - const I &gi, - int n, - I &r - ) - { - r.reset(); - int i, ir, jr; - FBV_UINT im, jm; - - jr = 0; jm = 1; - ir = 0; im = 1; - for ( i = 0; i < n; ++i ) - { - if ( mask.racks()[ir] & im ) - { - if ( gi.racks()[ir] & im ) - r.racks()[jr] |= jm; - jm<<=1; if ( jm == 0 ) { jm = 1; ++jr; } +template <class I> +inline void +grayCodeRank(const I& mask, const I& gi, int n, I& r) +{ + r.reset(); + + int jr = 0; + FBV_UINT jm = 1; + int ir = 0; + FBV_UINT im = 1; + for (int i = 0; i < n; ++i) { + if (mask.racks()[ir] & im) { + if (gi.racks()[ir] & im) { + r.racks()[jr] |= jm; + } + jm <<= 1; + if (jm == 0) { + jm = 1; + ++jr; } - - im<<=1; if ( im == 0 ) { im = 1; ++ir; } } - } + im <<= 1; + if (im == 0) { + im = 1; + ++ir; + } + } +} - template<class I> - inline - void - grayCodeRankInv( - const I &mask, - const I &ptrn, - const I &r, - int n, - int b, - I &g, - I &gi - ) - { - g.reset(); - gi.reset(); - - int i, j, ir, jr; - FBV_UINT im, jm; - - i = n-1; - BBV_MODSPLIT(ir,im,i); - im = (FBV1<<im); - - j = b-1; - BBV_MODSPLIT(jr,jm,j); - jm = (FBV1<<jm); - - FBV_UINT gi0, gi1, g0; - gi1 = gi0 = g0 = 0; - - for ( ; i >= 0; --i ) - { - // Unconstrained bit? - if ( mask.racks()[ir] & im ) - { - gi1 = gi0; - gi0 = (r.racks()[jr] & jm) > 0; - g0 = gi0 ^ gi1; - if ( gi0 ) gi.racks()[ir] |= im; - if ( g0 ) g.racks()[ir] |= im; - jm>>=1; if ( jm == 0 ) { jm=((FBV_UINT)1)<<(FBV_BITS-1); --jr; } +template <class I> +inline void +grayCodeRankInv(const I& mask, + const I& ptrn, + const I& r, + int n, + int b, + I& g, + I& gi) +{ + g.reset(); + gi.reset(); + + int ir, jr; + FBV_UINT im, jm; + + int i = n - 1; + BBV_MODSPLIT(ir, im, i); + im = (FBV1 << im); + + int j = b - 1; + BBV_MODSPLIT(jr, jm, j); + jm = (FBV1 << jm); + + FBV_UINT gi0, gi1, g0; + gi1 = gi0 = g0 = 0; + + for (; i >= 0; --i) { + // Unconstrained bit? + if (mask.racks()[ir] & im) { + gi1 = gi0; + gi0 = (r.racks()[jr] & jm) > 0; + g0 = gi0 ^ gi1; + if (gi0) { + gi.racks()[ir] |= im; + } + if (g0) { + g.racks()[ir] |= im; + } + jm >>= 1; + if (jm == 0) { + jm = ((FBV_UINT)1) << (FBV_BITS - 1); + --jr; } - else - { - g0 = (ptrn.racks()[ir] & im) > 0; - gi1 = gi0; - gi0 = g0 ^ gi1; - if ( gi0 ) gi.racks()[ir] |= im; - if ( g0 ) g.racks()[ir] |= im; + } else { + g0 = (ptrn.racks()[ir] & im) > 0; + gi1 = gi0; + gi0 = g0 ^ gi1; + if (gi0) { + gi.racks()[ir] |= im; } + if (g0) { + g.racks()[ir] |= im; + } + } - im>>=1; if ( im == 0 ) { im=((FBV_UINT)1)<<(FBV_BITS-1); --ir; } + im >>= 1; + if (im == 0) { + im = ((FBV_UINT)1) << (FBV_BITS - 1); + --ir; } } +} - - template <class I> - inline - void - extractMask( - const int *ms, - int n, - int d, - int i, - I &mask, - int &b - ) - { - assert( 0 <= d && d < n ); - int j, jr; - FBV_UINT jm; - - mask.reset(); - b = 0; - - jm = 1; jr = 0; - j = d; // #D j = (d==n-1) ? 0 : d+1; - do - { - if ( ms[j] > i ) - { - mask.racks()[jr] |= jm; - ++b; - } - - jm <<= 1; if ( jm == 0 ) { jm=1; ++jr; } - if ( ++j == n ) j = 0; +template <class I> +inline void +extractMask(const int* ms, int n, int d, int i, I& mask, int& b) +{ + assert(0 <= d && d < n); + + mask.reset(); + b = 0; + + FBV_UINT jm = 1; + int jr = 0; + int j = d; // #D j = (d==n-1) ? 0 : d+1; + do { + if (ms[j] > i) { + mask.racks()[jr] |= jm; + ++b; } - while ( j != d ); - } + + jm <<= 1; + if (jm == 0) { + jm = 1; + ++jr; + } + if (++j == n) { + j = 0; + } + } while (j != d); } +} // namespace chilbert #endif |