1 #if !defined HAVE_MIXEDRADIX_SL_GRAY_H__ 2 #define HAVE_MIXEDRADIX_SL_GRAY_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2012, 2013, 2014, 2015, 2018, 2019 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 #include "comb/mixedradix-sl-gray-rank.h" 9 10 #include "comb/mixedradix-aux.h" 11 #include "comb/is-mixedradix-num.h" 12 #include "comb/comb-print.h" 13 14 #include "fxttypes.h" 15 16 17 class mixedradix_sl_gray 18 // Mixed radix numbers in a minimal-change order 19 // related so subset-lex order ("SL-Gray" order). 20 // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) 21 // http://arxiv.org/abs/1405.6503 22 { 23 protected: 24 ulong n_; // Number of digits (n kinds of elements in multiset, n>=1) 25 ulong tr_; // aux: current track, index of last non-zero digit, 0 also for all-zero word 26 ulong * a_; // digits of mixed radix number (multiplicity of kind k in subset). 27 ulong * d_; // directions (either +1 or -1) 28 ulong * m1_; // nines (radix minus one) for each digit (multiplicity of kind k in superset). 29 30 ulong j_; // position of last change; returned by pos() 31 int dm_; // direction of last change; returned by dir() 32 33 mixedradix_sl_gray_rank * RU { nullptr }; // rank and unrank functions 34 35 private: // have pointer data 36 mixedradix_sl_gray(const mixedradix_sl_gray&) = delete; 37 mixedradix_sl_gray & operator = (const mixedradix_sl_gray&) = delete; 38 39 public: 40 explicit mixedradix_sl_gray(ulong n, ulong mm, const ulong *m = nullptr) 41 // Must have n>=1 42 { 43 n_ = n; 44 a_ = new ulong[n_+2]; // all with sentinels at both ends 45 d_ = new ulong[n_+2]; 46 m1_ = new ulong[n_+2]; 47 48 // sentinels on the right: 49 a_[n_+1] = +1; // != 0 50 m1_[n_+1] = +1; // same as a_[n+1] 51 d_[n_+1] = +1; // positive 52 53 // sentinels on the left: 54 a_[0] = +2; // >= +2 55 m1_[0] = +2; // same as a_[0] 56 d_[0] = 0; // zero 57 58 ++a_; ++d_; ++m1_; // nota bene 59 60 mixedradix_init(n_, mm, m, m1_); 61 62 RU = new mixedradix_sl_gray_rank( data(), num_digits(), nines() ); 63 64 first(); 65 } 66 ~mixedradix_sl_gray()67 ~mixedradix_sl_gray() 68 { 69 --a_; --d_; --m1_; 70 delete [] a_; 71 delete [] d_; 72 delete [] m1_; 73 delete RU; 74 } 75 data()76 const ulong * data() const { return a_; } nines()77 const ulong * nines() const { return m1_; } directions()78 const ulong * directions() const { return d_; } num_digits()79 ulong num_digits() const { return n_; } track()80 ulong track() const { return tr_; } // index of rightmost non-zero digit pos()81 ulong pos() const { return j_; } // position of last change dir()82 int dir() const { return dm_; } // direction of last change 83 first()84 void first() 85 { 86 for (ulong k=0; k<n_; ++k) a_[k] = 0; 87 for (ulong k=0; k<n_; ++k) d_[k] = +1; 88 tr_ = 0; 89 90 j_ = 0; // arbitrary 91 dm_ = -1; // arbitrary 92 } 93 94 next()95 bool next() 96 // Generate next. 97 // Return false if current was last. 98 // Loopless if all radices are even and >= 4 because all 99 // successive changes are at a distance of at most 2 (two-close 100 // Gray code), also for radix 2 as the Gray code is three-close. 101 { 102 ulong j = tr_; 103 const ulong dj = d_[j]; 104 const ulong a1 = a_[j] + dj; // a[j] +- 1 105 106 // if ( (a1 != 0) && (a1 <= m1_[j]) ) // easy case 107 if ( a1 - 1 < m1_[j] ) // easy case (optimized) 108 { 109 a_[j] = a1; 110 j_ = j; // record position of change 111 dm_ = (int)dj; // record direction of change 112 return true; 113 } 114 115 d_[j] = -dj; // change direction 116 117 if ( dj == +1 ) // so a_[j] == m1_[j] == nine 118 { 119 // Try to move track right with a[j] == nine: 120 const ulong j1 = j + 1; 121 if ( a_[j1] == 0 ) // can read high sentinel 122 { 123 a_[j1] = +1; 124 tr_ = j1; 125 j_ = j1; // record position of change 126 dm_ = +1; // record direction of change 127 return true; 128 } 129 } 130 else // here dj == -1, so a_[j] == 1 131 { 132 if ( (long)j <= 0 ) return false; // current is last 133 134 // Try to move track left with a[j] == 1: 135 const ulong j1 = j - 1; 136 if ( a_[j1] == m1_[j1] ) // can read low sentinel when n_ == 1 137 { 138 a_[j] = 0; 139 d_[j1] = -1UL; 140 tr_ = j1; 141 j_ = j1; // record position of change 142 dm_ = -1; // record direction of change 143 return true; 144 } 145 } 146 147 // find first changeable track to the left: 148 --j; 149 while ( a_[j] + d_[j] > m1_[j] ) // may read low sentinels 150 { 151 d_[j] = -d_[j]; // change direction 152 --j; 153 } 154 155 if ( (long)j < 0 ) return false; // current is last 156 157 // Change digit left but keep track: 158 a_[j] += d_[j]; 159 160 j_ = j; // record position of change 161 dm_ = (int)d_[j]; // record direction of change 162 163 return true; 164 } 165 166 // void last() 167 // { 168 // ulong e = 1; // rank of last number 169 // for (ulong j=0; j<n_; ++j) e *= (m1_[j] + 1); 170 // e -= 1; 171 // unrank( e ); 172 // } 173 174 // bool prev() 175 // // Generate previous. 176 // // Return false if current was first. 177 // { // Same as next() but direction d[] negated 178 // } 179 card()180 ulong card() const 181 // Cardinality of current subset (sum of digits). 182 { 183 ulong s = 0; 184 for (ulong j=0; j<n_; ++j) s += a_[j]; 185 return s; 186 } 187 rank()188 ulong rank() const 189 { 190 return RU->rank(); 191 } 192 unrank(ulong r)193 void unrank(ulong r) 194 // Invalidates pos() and dir() 195 { 196 tr_ = RU->unrank( r, a_ ); 197 } 198 199 void print(const char *bla, bool dfz=false) const 200 // If dfz is true then Dots are printed For Zeros. 201 { print_mixedradix(bla, a_, n_, dfz); } 202 print_nines(const char * bla)203 void print_nines(const char *bla) const 204 { print_mixedradix(bla, m1_, n_, false); } 205 OK()206 bool OK() const 207 { 208 if ( ! is_mixedradix_num(a_, n_, m1_) ) return false; 209 210 const ulong rk = RU->rank(); 211 ulong B[n_]; 212 RU->unrank( rk, B ); 213 for (ulong j=0; j<n_; ++j) 214 if ( data()[j] != B[j] ) 215 return false; 216 217 return true; 218 } 219 }; 220 // ------------------------- 221 222 223 224 #endif // !defined HAVE_MIXEDRADIX_SL_GRAY_H__ 225