HuffmanCoding

"use strict"
function node(inp_name, inp_fr, inp_used, inp_code, inp_link){
    this.name = inp_name;
    this.frequency = inp_fr;
    this.used = inp_used;
    this.code = inp_code;
    this.link = inp_link;
}


function Encode(message) {
    let alphabet = GetAlphabetWithFrequency(message);
    let HuffmanTree = CreateLeavesHuffmanTree(alphabet);
    CreateBranchVertexesHuffmanTree(HuffmanTree);
    let codeTable = CreateCodeTable(HuffmanTree);
    let encodedMessage = "";
    for (let i = 0; i < message.length; i++){
        encodedMessage += codeTable[message[i]];
    }
    return encodedMessage;
}


function GetAlphabetWithFrequency(message) {
    let alphabet = new Array();
    for(let i = 0; i < message.length; i++) {
        let letter = message.charAt(i);
        if ([letter] in alphabet) {
            alphabet[letter] += 1;
        } else {
            alphabet[letter] = 1;
        }
    }
    return alphabet;
}


function CreateLeavesHuffmanTree(alphabet) {
    let tree = new Array();
    for (let letter in alphabet) {
        tree.push(new node(letter, alphabet[letter], false, '', null));
    }
    return tree;
}


function CreateBranchVertexesHuffmanTree(tree) {
    let amountOfNotUsedVertexes = tree.length;
    while (true) {
        let mins = GetNotUsedFirstMinAndSecondMin(tree);
        let firstMin = mins[0]; let secondMin = mins[1];

        let combName = firstMin.name + secondMin.name;
        let combFrequency = firstMin.frequency + secondMin.frequency;
        let combIndex = tree.length;

        tree[combIndex] = new node(combName, combFrequency, false, '', combIndex);
        UpdateUsedVertexes(firstMin, secondMin, combIndex);
        amountOfNotUsedVertexes += 1 - 2;
        if (amountOfNotUsedVertexes == 1) break;
    }
}


function GetNotUsedFirstMinAndSecondMin(tree) {
    let firstMin = new node("", +Infinity, false, '', NaN);
    let secondMin = new node("", +Infinity, false, '', NaN);
    for (let i = 0; i < tree.length; i++) {
        if (!tree[i].used && (tree[i].frequency < firstMin.frequency)) {
            secondMin = firstMin;
            firstMin = tree[i];
        } else if (!tree[i].used && (tree[i].frequency < secondMin.frequency)) {
            secondMin = tree[i];
        }
    }
    return [firstMin, secondMin];
}


function UpdateUsedVertexes(firstMin, secondMin, combinationNodeIndex) {
    firstMin.used = true; firstMin.code = "0"; firstMin.link = combinationNodeIndex;
    secondMin.used = true; secondMin.code = "1"; secondMin.link = combinationNodeIndex;
}


function CreateCodeTable(tree) {
    let codeTable = {};
    for(let i = 0; i < tree.length; i++) {
        if (tree[i].name.length != 1) continue;
        let code = ReadCode(tree[i], tree);
        codeTable[tree[i].name] = reverseString(code);
    }
    return codeTable;
}


function ReadCode(letterNode, tree) {
    let code = letterNode.code;
    let nextNodeIndex = letterNode.link;
    while (tree[nextNodeIndex].used) {
        code += tree[nextNodeIndex].code;
        nextNodeIndex = tree[nextNodeIndex].link;
    }
    return code;
}


function reverseString(string) {
    let result = "";
    for (let i = string.length - 1; i >= 0; i--) {
        result += string[i];
    }
    return result;
}


test();
function test() {
    let str = 'abraсadabra';
    let a = GetAlphabetWithFrequency(str);
    let b = CreateLeavesHuffmanTree(a);
    let x = CreateBranchVertexesHuffmanTree(b);
    let e = Encode(str);
    console.log(e.length);
}