Mercurial > hg
comparison tests/test-revlog-raw.py @ 31763:8a0c47982ade
test-revlog-raw: fix "genbits" implementation
The "genbits" implementation is actually incorrect. This patch fixes it. A
good "genbits" implementation should pass the below assertion:
n = 3 # or other number
l = list(genbits(n))
assert 2**(n*2) == len(set((l[i]<<n)+l[i+1] for i in range(len(l)-1)))
An assertion is added to make sure "genbits" won't work unexpectedly.
author | Jun Wu <quark@fb.com> |
---|---|
date | Sun, 02 Apr 2017 18:12:47 -0700 |
parents | 985de02b5b9d |
children | 15707e58fc3d |
comparison
equal
deleted
inserted
replaced
31762:dff03f68ef11 | 31763:8a0c47982ade |
---|---|
164 ''' | 164 ''' |
165 m = 2 ** n | 165 m = 2 ** n |
166 | 166 |
167 # Gray Code. See https://en.wikipedia.org/wiki/Gray_code | 167 # Gray Code. See https://en.wikipedia.org/wiki/Gray_code |
168 gray = lambda x: x ^ (x >> 1) | 168 gray = lambda x: x ^ (x >> 1) |
169 reversegray = dict((gray(i), i) for i in range(m)) | |
169 | 170 |
170 # Generate (n * 2) bit gray code, yield lower n bits as X, and look for | 171 # Generate (n * 2) bit gray code, yield lower n bits as X, and look for |
171 # the next unused gray code where higher n bits equal to X. | 172 # the next unused gray code where higher n bits equal to X. |
172 | 173 |
173 # For gray codes whose higher bits are X, a[X] of them have been used. | 174 # For gray codes whose higher bits are X, a[X] of them have been used. |
175 | 176 |
176 # Iterate from 0. | 177 # Iterate from 0. |
177 x = 0 | 178 x = 0 |
178 yield x | 179 yield x |
179 for i in range(m * m): | 180 for i in range(m * m): |
181 x = reversegray[x] | |
180 y = gray(a[x] + x * m) & (m - 1) | 182 y = gray(a[x] + x * m) & (m - 1) |
183 assert a[x] < m | |
181 a[x] += 1 | 184 a[x] += 1 |
182 x = y | 185 x = y |
183 yield x | 186 yield x |
184 | 187 |
185 def gentext(rev): | 188 def gentext(rev): |