Skip to content

Instantly share code, notes, and snippets.

@donnut
Forked from jcoglan/bitmapped_vector_trie.js
Created August 26, 2014 11:39
Show Gist options
  • Save donnut/d5f8ab2426fd3aad273c to your computer and use it in GitHub Desktop.
Save donnut/d5f8ab2426fd3aad273c to your computer and use it in GitHub Desktop.
var BVT = function(width, depth, init, elems) {
this._width = width;
this._depth = depth;
this._leaf = depth === 1;
this._shift = (this._depth - 1) * Math.round(Math.log(width) / Math.log(2));
this._himask = this._width - 1;
this._lomask = Math.pow(2, this._shift) - 1;
this._elems = elems;
if (this._elems) return;
this._elems = new Array(width);
while (width--) {
if (this._leaf) {
this._elems[width] = init;
} else {
this._elems[width] = new BVT(this._width, depth - 1, init);
}
}
};
BVT.prototype.get = function(index) {
var offset = (index >>> this._shift) & this._himask,
elem = this._elems[offset];
if (this._leaf) {
return elem;
} else {
return elem.get(index & this._lomask);
}
};
BVT.prototype.set = function(index, value) {
var offset = (index >>> this._shift) & this._himask,
elems = this._elems.slice();
if (this._leaf) {
elems[offset] = value;
} else {
elems[offset] = elems[offset].set(index & this._lomask, value);
}
return new BVT(this._width, this._depth, 0, elems);
};
BVT.prototype.forEach = function(callback, context) {
if (this._leaf) {
this._elems.forEach(callback, context);
} else {
this._elems.forEach(function(sub) {
sub.forEach(callback, context);
});
}
};
BVT.prototype.toArray = function() {
var array = [];
this.forEach(function(v) { array.push(v) });
return array;
};
module.exports = BVT;
var BVT = require('./bitmapped_vector_trie'),
JS = require('jstest')
JS.Test.describe('Bitmapped vector trie', function() { with(this) {
before(function() { with(this) {
this.bvt = new BVT(4, 4, 0)
}})
it('reads a value at an index', function() { with(this) {
assertEqual( 0, bvt.get(0) )
}})
it('sets a value at an index', function() { with(this) {
this.bvt = bvt.set(12, 1)
assertEqual( 1, bvt.get(12) )
}})
it('returns a new structure', function() { with(this) {
assertNotSame( bvt.set(12 ,1), bvt )
}})
it('preserves the original structure', function() { with(this) {
var newbvt = bvt.set(12, 1)
assertEqual( 0, bvt.get(12) )
assertEqual( 1, newbvt.get(12) )
}})
}})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment