<commit_before>#include "Huffman.hpp"

Node::Node(double probability, Node* left, Node* right)
    : probability(probability),
    left(left),
    right(right),
    is_leaf(false)
{}

Node::Node(double probability, int symbol)
    : probability(probability),
    symbol(symbol),
    is_leaf(true),
    left(nullptr),
    right(nullptr)
{}

Node::~Node() {
    delete left;
    delete right;
}

int Node::height() const {
    if (is_leaf)
        return 0;
    else if (left && right)
        return std::max(left->height(), right->height()) + 1;
    else if (left)
        return left->height() + 1;
    else
        return right->height() + 1;
}


Node* generate_huff_tree(unordered_map<int, int> symbol_counts, int total) {
    auto comp = [](const Node* lhs, const Node* rhs) {
        return lhs->probability > rhs->probability;
    };
    priority_queue<Node*, vector<Node*>, decltype(comp)> nodes;

    // create a leaf node for every symbol
    // also calculate it's probability from the given count and total
    for (const auto& pair : symbol_counts) {
        // pair.first: symbol
        // pair.second: count
        nodes.emplace(new Node((double)pair.second / (double)total, pair.first));
    }

    // combine the two nodes with lowest probability into a new one till only one is left
    while (nodes.size() > 1) {
        // least probable symbol or node
        Node* first = nodes.top();
        nodes.pop();
        // second least probable symbol or node
        Node* second = nodes.top();
        nodes.pop();

        // always put the higher tree to the right
        if (first->height() > second->height()) {
            std::swap(first, second);
        }
        nodes.emplace(new Node(first->probability + second->probability, first, second));
    }

    Node* root = nodes.top();
    // handle the case where we only have a single symbol
    if (root->is_leaf)
        return new Node(root->probability, root, nullptr);
    else
        return root;
}


void replace_rightmost_leaf(Node* root) {
    assert(root != nullptr);

    Node* node = root;
    Node* parent = nullptr;

    while (node->right) {
        parent = node;<commit_msg>Removed height check and swap when creating a huffman tree. Didn't work.<commit_after>#include "Huffman.hpp"

Node::Node(double probability, Node* left, Node* right)
    : probability(probability),
    left(left),
    right(right),
    is_leaf(false)
{}

Node::Node(double probability, int symbol)
    : probability(probability),
    symbol(symbol),
    is_leaf(true),
    left(nullptr),
    right(nullptr)
{}

Node::~Node() {
    delete left;
    delete right;
}

int Node::height() const {
    if (is_leaf)
        return 0;
    else if (left && right)
        return std::max(left->height(), right->height()) + 1;
    else if (left)
        return left->height() + 1;
    else
        return right->height() + 1;
}


Node* generate_huff_tree(unordered_map<int, int> symbol_counts, int total) {
    auto comp = [](const Node* lhs, const Node* rhs) {
        return lhs->probability > rhs->probability;
    };
    priority_queue<Node*, vector<Node*>, decltype(comp)> nodes;

    // create a leaf node for every symbol
    // also calculate it's probability from the given count and total
    for (const auto& pair : symbol_counts) {
        // pair.first: symbol
        // pair.second: count
        nodes.emplace(new Node((double)pair.second / (double)total, pair.first));
    }

    // combine the two nodes with lowest probability into a new one till only one is left
    while (nodes.size() > 1) {
        // least probable symbol or node
        Node* first = nodes.top();
        nodes.pop();
        // second least probable symbol or node
        Node* second = nodes.top();
        nodes.pop();

        nodes.emplace(new Node(first->probability + second->probability, first, second));
    }

    Node* root = nodes.top();
    // handle the case where we only have a single symbol
    if (root->is_leaf)
        return new Node(root->probability, root, nullptr);
    else
        return root;
}


void replace_rightmost_leaf(Node* root) {
    assert(root != nullptr);

    Node* node = root;
    Node* parent = nullptr;

    while (node->right) {
        parent = node;
{'fraction_non_alphanumeric': 0.12847058823529411, 'fraction_numerical': 0.002352941176470588, 'mean_word_length': 2.5934065934065935, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3549384', 'n_tokens_mistral': 1282, 'n_tokens_neox': 1257, 'n_words': 389}