Nonconformist Propaganda Machine
    Share your code. npm Orgs help your team discover, share, and reuse code. Create a free org »

    bit-vector.jsxpublic

    bit-vector.jsx

    Build Status

    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

    Use from JSX

    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.set1(2);
            bv.set1(3);
            bv.set1(6):
            bv.build(); // 00110010
     
            console.log(bv.rank1(0)); // -> 0
            console.log(bv.rank1(1)); // -> 0
            console.log(bv.rank1(2)); // -> 1
            console.log(bv.rank1(3)); // -> 2
            console.log(bv.rank1(4)); // -> 2
            console.log(bv.rank1(5)); // -> 2
            console.log(bv.rank1(6)); // -> 3
            console.log(bv.rank1(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.rank1(pos)]; // => 500; Same value!
     
            // Select: return x-th bit from first
            console.log(bv.select1(0)); // -> 0
            console.log(bv.select1(1)); // -> 2
            console.log(bv.select1(2)); // -> 3
            console.log(bv.select1(3)); // -> 6
     
            // Find the word that specified character belongs to.
            var words = "hello world succinct bit vector";
            var bv2 = new Uint32BitVector(words.length);
            bv.set1(6);
            bv.set1(12);
            bv.set1(21);
            bv.set1(25);
            bv.build();
     
            console.log(bv.select(10)); // -> 1: 10th character belongs to second word.
        }
    }

    Use from node.js

    var ArrayBitVector = require('bit-vector.common.js').ArrayBitVector;
    var Uint32BitVector = require('bit-vector.common.js').Uint32BitVector;

    Use from require.js

    // use bit-vector.amd.js
    define(['bit-vector.jsx'], function (bitvector) {
        ArrayBitVector = bitvector.ArrayBitVector;
        Uint32BitVector = bitvector.Uint32BitVector;
    });

    Use via standard JSX function

    <script src="bit-vector.js" type="text/javascript"></script>
    <script type="text/javascript">
    window.onload = function () {
        var ArrayBitVector = JSX.require("src/bit-vector.js").ArrayBitVector;
        var Uint32BitVector = JSX.require("src/bit-vector.js").Uint32BitVector;
    });
    </script> 

    Use via global variables

    <script src="bit-vector.global.js" type="text/javascript"></script>
    <script type="text/javascript">
    window.onload = function () {
        var bv = new ArrayBitVector();
        var bv2 = new Uint32BitVector(10);
    });
    </script> 

    Installation

    $ npm install bit-vector.jsx

    If you want to use this library from other JSX project, install like the following:

    $ npm install bit-vector.jsx --save-dev

    or add like these lines to your parent project's package.json:

       devDependencies: {
           "bit-vector.jsx": "~0.4.0"
       },
       peerDepenencies: {
           "bit-vector.jsx": "~0.4.0"
       }

    And add node_modules/bit-vector.jsx/src as a search path.

    API Reference

    abstract class BitVector

    This is an abstract of the following classes.

    BitVector.create(size : int) : BitVector

    Creates new object and returns. If the environment supports Uint32Array, it returns Uint32BitVector object. Otherwise, it returns Array32BitVector object.

    BitVector.load(input : BinaryInput) : BitVector

    Load from BinaryInput. If the environment supports Uint32Array, it returns Uint32BitVector object. Otherwise, it returns Array32BitVector object.

    class ArrayBitVector extends BitVector

    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.

    class Uint32BitVector(size : int) extends BitVector

    Constructor for bit vector based on Uint32bitVector. This version is fixed size, but memory efficiency is better than ArrayBitVector.

    BitVector#size() : int

    It returns BitVector size. set extends this size.

    BitVector#size0() : int

    It returns number of 0 bit in BitVector.

    BitVector#size1() : int

    It returns number of 1 bit in BitVector.

    BitVector#set0(pos : int) : void

    It sets bit at the specified position.

    BitVector#set1(pos : int) : void

    It clears bit at the specified position.

    BitVector#get(pos : int) : boolean

    It returns bit of specified position.

    BitVector#build() : void

    Precalculates rank() number. It should be called before using select() and rank().

    BitVector#rank0(pos : int) : int

    Counts number of 0 bit before specified position.

    BitVector#rank1(pos : int) : int

    Counts number of 1 bit before specified position.

    BitVector#select0(pos : int) : int

    Returns x-th 0 bit from first.

    BitVector#select1(pos : int) : int

    Returns x-th 1 bit from first.

    BitVector#dump(output : BinaryOutput) : void

    Export bit-vector.

    BitVector#load(input : BinaryInput) : void

    Import bit-vector.

    Development

    JSX

    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.

    Setup

    To create development environment, call following command:

    $ npm install

    Repository

    • Repository: git:/github.com/shibukawa/bit-vector.jsx.git
    • Issues: Repository: https:/github.com/shibukawa/bit-vector.jsx/issues

    Run Test

    $ grunt test

    Build

    $ grunt build

    Generate API reference

    $ grunt doc

    Author

    License

    MIT

    Complete license is written in LICENSE.md.

    Keywords

    none

    install

    npm i bit-vector.jsx

    Downloadsweekly downloads

    23

    version

    0.4.0

    license

    none

    repository

    githubgit:

    last publish

    collaborators

    • avatar