Skip to content

Instantly share code, notes, and snippets.

@estliberitas
Created June 1, 2015 08:37
Show Gist options
  • Save estliberitas/98647a02a23c59e8b9a0 to your computer and use it in GitHub Desktop.
Save estliberitas/98647a02a23c59e8b9a0 to your computer and use it in GitHub Desktop.
JavaScript cool-lex implementation
// Below 3 versions of cool-lex loopless algorithm are listed.
// The only difference between them is data structure used to
// store a bit string: Number, Array, Buffer (node.js).
//
// Number version, as you may guess, will work properly for
// s + t < 32 thus bitwise / shift operators operate on 32bit
// integers.
function coollexArray(s, t, cb) {
var x = 0;
var n = s + t;
var b = new Array(n);
while (x < t) {
b[x++] = 1;
}
while (x < n) {
b[x++] = 0;
}
x = t - 1;
var y = t - 1;
while (x < n) {
b[x] = 0;
b[y] = 1;
x++;
y++;
if (x < n && b[x] === 0) {
b[x] = 1;
b[0] = 0;
if (y > 1) {
x = 1;
}
y = 0;
}
cb(b);
}
}
function coollexBitString(s, t, cb) {
var x = 0;
var n = s + t;
var b = 0;
while (x++ < t) {
b <<= 1;
b |= 1;
}
x = t - 1;
var y = t - 1;
while (x < n) {
b &= ~(1 << x);
b |= 1 << y;
x++;
y++;
if (x < n && ((b >> x) & 1) === 0) {
b |= 1 << x;
b &= ~(1 << 0);
if (y > 1) {
x = 1;
}
y = 0;
}
cb(b);
}
}
function coollexBuffer(s, t, cb) {
var x = 0;
var n = s + t;
var b = new Buffer(n);
while (x < t) {
b[x++] = 1;
}
while (x < n) {
b[x++] = 0;
}
x = t - 1;
var y = t - 1;
while (x < n) {
b[x] = 0;
b[y] = 1;
x++;
y++;
if (x < n && b[x] === 0) {
b[x] = 1;
b[0] = 0;
if (y > 1) {
x = 1;
}
y = 0;
}
cb(b);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment