BitVector implementation in JSX.

bit_vector.jsx

/**
 * This is a JSX version of shellinford library:
 * https://code.google.com/p/shellinford/
 *
 * License: http://shibu.mit-license.org/
 */

class BitVector
{
    static const SMALL_BLOCK_SIZE : int =  32;
    static const LARGE_BLOCK_SIZE : int = 256;
    static const BLOCK_RATE       : int =   8;

    var _v : int[];
    var _r : int[];
    var _size : int;
    var _size1 : int;

    function constructor ()
    {
        this.clear();
    }

    function build () : void
    {
        this._r = [] : int[];
        this._size1 = 0;
        for (var i = 0; i < this._v.length; i++)
        {
            if (i % BitVector.BLOCK_RATE == 0)
            {
                this._r.push(this.size(true));
            }
            this._size1 += this._rank32(this._v[i], BitVector.SMALL_BLOCK_SIZE, true);
        }
    }

    function clear () : void
    {
        this._v = [] : int[];
        this._r = [] : int[];
        this._size = 0;
        this._size1 = 0;
    }

    function size () : int
    {
        return this._size;
    }

    function size (b : boolean) : int
    {
        return b ? (this._size1) : (this._size - this._size1);
    }

    function set (value : int, flag : boolean) : void
    {
        if (value >= this.size())
        {
            this._size = value + 1;
        }
        var q : int = value / BitVector.SMALL_BLOCK_SIZE;
        var r : int = value % BitVector.SMALL_BLOCK_SIZE;
        while (q >= this._v.length)
        {
            this._v.push(0);
        }
        var m : int = 0x1 << r;
        if (flag)
        {
            this._v[q] |=  m;
        }
        else
        {
            this._v[q] &= ~m;
        }
    }

    function get (value : int) : boolean
    {
        if (value >= this.size())
        {
            throw new Error("BitVector::get(): RangeError");
        }
        var q : int = value / BitVector.SMALL_BLOCK_SIZE;
        var r : int = value % BitVector.SMALL_BLOCK_SIZE;
        var m : int = 0x1 << r;
        return (this._v[q] & m) as boolean;
    }

    function rank (i : int) : int
    {
        return this.rank(i, true);
    }

    function rank (i : int, b : boolean) : int
    {
        if (i > this.size())
        {
            throw new Error("BitVector::rank(): RangeError");
        }
        if (i == 0)
        {
            return 0;
        }
        i--;
        var q_large : int = i / BitVector.LARGE_BLOCK_SIZE;
        var q_small : int = i / BitVector.SMALL_BLOCK_SIZE;
        var r       : int = i % BitVector.SMALL_BLOCK_SIZE;
        var rank : int = this._r[q_large];
        if (!b)
        {
            rank = q_large * BitVector.LARGE_BLOCK_SIZE - rank;
        }
        var begin = q_large * BitVector.BLOCK_RATE;
        for (var j = begin; j < q_small; j++)
        {
            rank += this._rank32(this._v[j], BitVector.SMALL_BLOCK_SIZE, b);
        }
        rank += this._rank32(this._v[q_small], r + 1, b);
        return rank;
    }

    function select(i : int) : int
    {
        return this.select(i, true);
    }

    function select(i : int, b : boolean) : int
    {
        return 1000;
    }

    function _rank32 (x : int, i : int, b : boolean) : int
    {
        if (!b)
        {
            x = ~x;
        }
        x <<= (BitVector.SMALL_BLOCK_SIZE - i);
        x = ((x & 0xaaaaaaaa) >>>  1)
          +  (x & 0x55555555);
        x = ((x & 0xcccccccc) >>>  2)
          +  (x & 0x33333333);
        x = ((x & 0xf0f0f0f0) >>>  4)
          +  (x & 0x0f0f0f0f);
        x = ((x & 0xff00ff00) >>>  8)
          +  (x & 0x00ff00ff);
        x = ((x & 0xffff0000) >>> 16)
          +  (x & 0x0000ffff);
        return x;
    }
}