Encoding selection of integers in a short, URL-friendly string

encode_selection.js

/* 

 A few functions for encoding a selection as a short, USL-friendly string.
 This can be used with history.js to update the URL based on the current selection and eventually decode it and display the relevant selection.

 NB MS won't like "const"

*/


    // To allow us to work with large integers,
    // we use an array of smaller integers, representing parts of the bits
    // This number is the number of bits per item
    const BITS_PER_ITEM = 30;

    // The URL-friendly alphabet used for base64 encoding
    // Using dot for zero, making "/./" and "/../" impossible
    const ALPHABET = '.123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-0';
    const BLOCK_LENGTH = ALPHABET.length.toString(2).length - 1;

    function encode(selection) {
        // Encode the currently selected filters into an integer
        var val = selection_to_integer(selection);

        // Compress and return as a base36 string
        return base64_encode(compress_sparse_binary(val));
    }

    function base64_encode(bin) { 
        var output = [];

        // Make sure we have blocks of six
        var padding = bin.length % BLOCK_LENGTH;
        if (padding > 0) {
            bin = Array(BLOCK_LENGTH+1-padding).join("0") + bin;
        }

        // Convert each block of six to a character
        for (var i=0; i < bin.length; i+=BLOCK_LENGTH) { 
            output.push(ALPHABET[parseInt(bin.slice(i, i+BLOCK_LENGTH),2)]);
        }

        return output.join("");
    }

    function selection_to_integer(selection) {
        // Remove invalid and duplicates
        var max_val = 0;
        var clean_selection = {};
        for (var i in selection) {
            var ival = selection[i];
            if (ival > 0) 
                clean_selection[ival] = true;
                max_val = ival > max_val ? ival : max_val;
        }
        // To avoid problems with javascript's number storage, we divide the bits
        // into an array. Each item has BITS_PER_ITEM bits.

        // Prepare result array
        var result = Array(Math.floor((max_val-1) / BITS_PER_ITEM) + 1);
        for (var i=0;i<result.length;i++) result[i] = 0;

        var val = 0;
        for (i in clean_selection) {
            var set = Math.floor((i-1) / BITS_PER_ITEM) + 1;
            var pos = ((i-1) % BITS_PER_ITEM);
            result[result.length-set] += (1 << pos);
        }
        return result;
    }


    const SEQUENCES_OF_ZERO = [
        [36, "00"],
        [6, "10"],
        [1, "01"],
    ];

    function compress_sparse_binary(val) {
        // Return an integer representing the given integer in a compressed format.
        // TODO work with bit operations instead of strings
        for (var i=0; i<val.length; i++) 
            if (i == 0) {
                val[i] = val[i].toString(2);
            } else {
                var item = (val[i] + (1 << BITS_PER_ITEM)).toString(2);
                val[i] = item.slice(1);
            }
        val = val.join("").split("");

        // Compress the result
        var output = [];
        while (val.length > 0) {
            var next_one = val.indexOf("1");
            if (next_one == -1) 
                next_one = val.length;
            // if the next "1" was here, handle it and move on
            if (next_one == 0) {
                val.shift();
                output[output.length] = "11";
                continue;
            }
            for (var i in SEQUENCES_OF_ZERO) {
                var v = SEQUENCES_OF_ZERO[i];
                var amount = v[0];
                var bits = v[1];
                while (next_one >= amount) {
                    val = val.splice(amount, val.length - amount);
                    output[output.length] = bits;
                    next_one -= amount;
                }
            }
        }
        return output.join("")
    }





//
// Unit tests
////////////////////////////////////////////////////////////////////////////////

assert = require('assert');

function test_selection_to_integer() {
    assert.equal(site.selection_to_integer([1])[0], parseInt("1", 2));
    assert.equal(site.selection_to_integer([1,4,5])[0], parseInt("11001", 2));
    assert.equal(site.selection_to_integer([2,3,5,3,8])[0], parseInt("10010110", 2));
    assert.equal(site.selection_to_integer([22])[0], parseInt("1000000000000000000000",2));
    // For a value higher than 30, the result is split into multipel integers
    var out_81 = site.selection_to_integer([81]);
    assert.equal(out_81[0], parseInt("100000000000000000000", 2));
    assert.equal(out_81[1], 0);
    assert.equal(out_81[2], 0);
}

function test_compress_sparse_binary() {
    assert.equal(site.compress_sparse_binary([parseInt("1000000000000000000000",2)]), "11101010010101");
    // For a larger value, 81
    assert.equal(site.compress_sparse_binary([parseInt("100000000000000000000",2), 0, 0]), "110000100101");
    assert.equal(site.compress_sparse_binary([parseInt("10010111", 2)]), "1101011101111111");
    assert.equal(site.compress_sparse_binary([parseInt("1000010001", 2)]), "11010101011101010111");
}

//
// System tests
////////////////////////////////////////////////////////////////////////////////

function test_system() {
    assert.equal(site.encode([22]), '3gL');
    assert.equal(site.encode([28]), 'EgL');
    assert.equal(site.encode([29]), 'wfL');
    assert.equal(site.encode([30]), '3gbL');
    assert.equal(site.encode([31]), 'wg');
    assert.equal(site.encode([32]), '3gf');
    assert.equal(site.encode([33]), 'Egb');
    assert.equal(site.encode([81]), 'mb');
    assert.equal(site.encode([1, 46, 119]), 'moN');
    assert.equal(site.encode([1, 46, 319]), '3..AboN');
    assert.equal(site.encode([1, 46, 519]), 'm...1LoN');
    assert.equal(site.encode([45, 46, 519]), 'm...1Lyb');
    assert.equal(site.encode([1, 76, 91, 17, 110]), '3gwNAbNfN');
    assert.equal(site.encode([1, 2, 3, 91, 92, 210]), 'C2LyAL0');
    assert.equal(site.encode([1, 76, 91, 17, 110]), '3gwNAbNfN');
    assert.equal(site.encode([1, 76, 91, 92, 93, 94, 17, 110, 195, 312]), 'm9SAwL0wNAbNfN');
    assert.equal(site.encode([1, 36, 71, 106, 141, 176, 211, 246, 281, 500]), 'm.5wgLUgbNgfLwgLUgbNgfLwgLUgbN');
}

test_selection_to_integer();
test_compress_sparse_binary();
test_system();

console.log("All tests passed");