/* Copyright (C) 2018 David Robillard Copyright (C) 2006-2007 Chris Hamilton This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #ifndef CHILBERT_GRAYCODERANK_HPP #define CHILBERT_GRAYCODERANK_HPP #include "chilbert/BigBitVec.hpp" #include "chilbert/FixBitVec.hpp" #include 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 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; } if (++j == n) { j = 0; } ++hi; } while (j != ds[i]); } } template 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; } } } template 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; } } im >>= 1; if (im == 0) { im = ((FBV_UINT)1) << (FBV_BITS - 1); --ir; } } } template 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; } jm <<= 1; if (jm == 0) { jm = 1; ++jr; } if (++j == n) { j = 0; } } while (j != d); } } // namespace chilbert #endif