bitmapped_vector_trie.js

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;

bitmapped_vector_trie_spec.js

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) )
  }})
}})