var alg = require("algorithms"),
    sort = alg.mergeSort;

/*
 * Huffman coding.
 *
 * @api public
 */

var huffman = function(alphabet){
    if(!(this instanceof huffman))
        return new huffman(alphabet);

    var syms = [],
        symtbl = {};

    for(var sym in alphabet){
        symtbl[sym] = null;
        syms.push({ obj: [sym], key: alphabet[sym] });
    }

    var cmp = function(a, b){ return a.key >= b.key },
        h = sort(syms, cmp);

    while(h.length !==  2){
        var fmin = h.pop(),
            smin = h.pop();

        var meta = smin.obj.concat(fmin.obj),
            key = fmin.key + smin.key;

        h.push({ obj: meta, key: key });
        h = sort(h, cmp);
    }

    var rsyms = h[0]["obj"],
        lsyms = h[1]["obj"],
        isone = false,
        split = function(array, base){
            if(array.length === 1){
                if(isone) symtbl[array[0]] = base + "0";
                else symtbl[array[0]] = base + "1";
            }else if(array.length === 2){
                var sym = array.shift();
                symtbl[sym] = base + "0";
                var sym = array.shift();
                symtbl[sym] = base + "1";
            }else{
                var sym = array.shift();
                symtbl[sym] = base + "0";
                split(array, base + "1");
            }

            isone = !isone;
            return;
        };

    if(lsyms.length === 1){
        symtbl[lsyms[0]] = "0";
        split(rsyms, "1");
    }else{
        split(lsyms, "0");
        split(rsyms, "1");
    }

    var luptbl = {};

    for(var i in symtbl){
        luptbl[symtbl[i]] = i;
    }

    this.symtbl = symtbl;
    this.luptbl = luptbl;
}

/*
 * Encode a string.
 *
 * @api public
 */

huffman.prototype.encode = function(str){
    if(Buffer.isBuffer(str))
        str = str.toString();

    var enc = [];

    for(var i = 0; i < str.length; i++){
        var code = this.symtbl[str[i]];
        if(code !== undefined){
            enc = enc.concat(code);
        }
    }

    return new Buffer(enc);
}

/*
 * Decode a buffer.
 *
 * @returns {String} decoded string
 *
 * @api public
 */

huffman.prototype.decode = function(buf){
    if(!Buffer.isBuffer(buf))
        buf = new Buffer(buf);

    var holder = "",
        out = ""
        luptbl = this.luptbl;

    for(var i = 0; i < buf.length; i++){
        var letter = buf[i];
        holder += letter;

        var decode = luptbl[holder];

        if(decode){
            out += decode;
            holder = "";
        }
    }

    return out;
}

// Exports
module.exports = huffman;