WaveletMatrix implementation in JSX.

wavelet_matrix.jsx

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

import "bit_vector.jsx";

class WaveletMatrix
{
    var _bv : BitVector[];
    var _seps : int[];
    var _range : Map.<int>;
    var _bitsize : int;
    var _size : int;

    function constructor (src : string)
    {
        this._range = {} : Map.<int>;
        this._bitsize = 16;
        this.clear();
        this.build(src);
    }

    function bitsize () : int
    {
        return this._bitsize;
    }

    function clear () : void
    {
        this._bv = [] : BitVector[];
        this._seps = [] : int[];
        this._size = 0;
    }

    function build (v : string) : void
    {
        this.clear();
        var size = v.length;
        var bitsize = this.bitsize();
        for (var i = 0; i < bitsize; i++)
        {
            this._bv.push(new BitVector);
            this._seps.push(0);
        }
        this._size = size;
        for (var i = 0; i < size; i++)
        {
            this._bv[0].set(i, this._uint2bit(v.charCodeAt(i), 0));
        }
        this._bv[0].build();
        this._seps[0] = this._bv[0].size(false);
        this._range[0 as string] = 0;
        this._range[1 as string] = this._seps[0];

        var depth : int = 1;
        while (depth < bitsize)
        {
            var range_tmp = this._shallow_copy(this._range); // copy
            for (var i = 0; i < size; i++)
            {
                var code = v.charCodeAt(i);
                var bit = this._uint2bit(code, depth);
                var key = code >>> (bitsize - depth);
                this._bv[depth].set(range_tmp[key as string], bit);
                range_tmp[key as string]++;
            }
            this._bv[depth].build();
            this._seps[depth] = this._bv[depth].size(false);

            var range_rev = {} : Map.<int>;
            for (var range_key in this._range)
            {
                var value : int = this._range[range_key];
                if (value != range_tmp[range_key])
                {
                    range_rev[value as string] = range_key as int;
                }
            }
            this._range = {} : Map.<int>;
            var pos0 = 0;
            var pos1 = this._seps[depth];
            for (var range_rev_key in range_rev)
            {
                var begin = range_rev_key as int;
                var value = range_rev[range_rev_key];
                var end = range_tmp[value as string];
                var num0  = this._bv[depth].rank(end  , false) -
                            this._bv[depth].rank(begin, false);
                var num1  = end - begin - num0;
                if (num0 > 0)
                {
                    this._range[(value << 1) as string] = pos0;
                    pos0 += num0;
                }
                if (num1 > 0)
                {
                    this._range[((value << 1) + 1) as string] = pos1;
                    pos1 += num1;
                }
            }
            depth++;
        }
    }

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

    function size (c : int) : int
    {
        return this.rank(this.size(), c);
    }

    function get (i : int) : int
    {
        if (i >= this.size())
        {
            throw "shellinford::wavelet_matrix::get()";
        }
        var value = 0;
        var depth = 0;
        while (depth < this.bitsize())
        {
            var bit = this._bv[depth].get(i);
            i = this._bv[depth].rank(i, bit);
            value <<= 1;
            if (bit)
            {
                i += this._seps[depth];
                value += 1;
            }
            depth++;
        }
        return value;
    }

    function rank (i : int, c : int) : int
    {
        if (i > this.size())
        {
            throw new Error("WaveletMatrix::rank(): range error");
        }
        if (i == 0)
        {
            return 0;
        }

        var begin = this._range[c as string];
        if (begin == null)
        {
            return 0;
        }
        var end   = i;
        var depth = 0;
        while (depth < this.bitsize())
        {
            var bit = this._uint2bit(c, depth);
            end = this._bv[depth].rank(end, bit);
            if (bit)
            {
                end += this._seps[depth];
            }
            depth++;
        }
        return end - begin;
    }

    function rank_less_than (i : int, c : int) : int
    {
        if (i > this.size())
        {
            throw new Error("WaveletMatrix::rank_less_than(): range error");
        }
        if (i == 0)
        {
            return 0;
        }

        var begin = 0;
        var end   = i;
        var depth = 0;
        var rlt   = 0;
        while (depth < this.bitsize())
        {
            var rank0_begin = this._bv[depth].rank(begin, false);
            var rank0_end   = this._bv[depth].rank(end  , false);
            if (this._uint2bit(c, depth))
            {
                rlt += (rank0_end - rank0_begin);
                begin += (this._seps[depth] - rank0_begin);
                end   += (this._seps[depth] - rank0_end);
            }
            else
            {
                begin = rank0_begin;
                end   = rank0_end;
            }
            depth++;
        }
        return rlt;
    }

    function _shallow_copy (input : Map.<int>) : Map.<int>
    {
        var result = {} : Map.<int>;
        for (var key in input)
        {
            result[key] = input[key];
        }
        return result;
    }

    function _uint2bit(c : int, i : int) : boolean
    {
        return ((c >>> (16 - 1 - i)) & 0x1) == 0x1;
    }
}