BitVector implementation for JSX/JS/AMD/CommonJS
npm install bit-vector.jsxbit-vector.jsx
===========================================
Synopsis
---------------
Succinct Bit Vector implementation for JSX/JS/AMD/CommonJS
Motivation
---------------
This code is a part of Oktavia. Bit Vector is used to reduce memory foot print to store suffix array and
provides some high speed operation in O(1) - O(N).
Code Example
---------------
``js
import "bit-vector.jsx";
class _Main {
static function main(argv : string[]) : void
{
// Rank: number of bits before specified position
var bv = new Uint32BitVector(8);
bv.set(2);
bv.set(3);
bv.set(6):
bv.build(); // 00110010
console.log(bv.rank(0)); // -> 0
console.log(bv.rank(1)); // -> 0
console.log(bv.rank(2)); // -> 1
console.log(bv.rank(3)); // -> 2
console.log(bv.rank(4)); // -> 2
console.log(bv.rank(5)); // -> 2
console.log(bv.rank(6)); // -> 3
console.log(bv.rank(7)); // -> 3
// Compress array that has many empty spaces by using BitVector.rank()
var original = [0, 0, 200, 300, 0, 0, 500, 0]; < 8 x 8 = 64 byte
var pos = 7;
var getNum = original[pos]; // => 500;
var values = [200, 300, 500]; // => 24 byte + 4 byte(uint32).
var getNum2 = values[bv.rank(pos)]; // => 500; Same value!
// Select: return x-th bit from first
console.log(bv.select(0)); // -> 0
console.log(bv.select(1)); // -> 2
console.log(bv.select(2)); // -> 3
console.log(bv.select(3)); // -> 6
// Find the word that specified character belongs to.
var words = "hello world succinct bit vector";
var bv2 = new Uint32BitVector(words.length);
bv.set(6);
bv.set(12);
bv.set(21);
bv.set(25);
bv.build();
console.log(bv.select(10)); // -> 1: 10th character belongs to second word.
}
}
`
`js`
var ArrayBitVector = require('bit-vector.common.js').ArrayBitVector;
var Uint32BitVector = require('bit-vector.common.js').Uint32BitVector;
`js
// use bit-vector.amd.js
define(['bit-vector.jsx'], function (bitvector) {
ArrayBitVector = bitvector.ArrayBitVector;
Uint32BitVector = bitvector.Uint32BitVector;
});
`
`html`
`html`
Installation
---------------
`sh`
$ npm install bit-vector.jsx
API Reference
------------------
Constructor for bit vector based on int[]. This version resizes length automatically, but each only memory efficiency is 50%.
This is JavaScript limitation because it has only 64bit floating point number and it uses only 32bit part as integer.
Constructor for bit vector based on Uint32bitVector. This version is fixed size, but memory efficiency is better than ArrayBitVector.
It returns BitVector size. set extends this size.
It sets bit. If flag is false, it inverts bit at specified position.
It returns bit of specified position.
Precalculates rank() number. It should be called before using select() and rank().
Counts number of bits before specified position. If flag is false it calcs count inverted bits.
Returns x-th bit from first. If flag is false it returns position of specified x-th inverted bits.
Development
-------------
Don't afraid JSX! If you have an experience of JavaScript, you can learn JSX
quickly.
* Static type system and unified class syntax.
* All variables and methods belong to class.
* JSX includes optimizer. You don't have to write tricky unreadalbe code for speed.
* You can use almost all JavaScript API as you know. Some functions become static class functions. See reference.
To create development environment, call following command:
`sh`
$ npm install
* Repository: git:/github.com/shibukawa/bit-vector.jsx.git
* Issues: Repository: https:/github.com/shibukawa/bit-vector.jsx/issues
`sh`
$ grunt test
`sh`
$ grunt build
`sh`
$ grunt doc
Author
---------
* shibukawa / yoshiki@shibu.jp
License
------------
MIT
Complete license is written in LICENSE.md`.