<commit_before>#include "PackageMerge.hpp"
#include <map>

Node* PackageMerge::generate(const std::vector<Node*> &input, unsigned short limit) {
	nodesListOriginal.clear();
	for (Node *n : input)
		nodesListOriginal.push_back( PackageNode(n->symbol, n->frequency) );
	
	// start off with the original list and evolve package list with each level
	nodesListPackaged = nodesListOriginal;
	
	for (int i = limit; i > 0; --i) {
		package();
		if (i > 1) // why should we merge in the last step? (just all symbols +1)
			merge();
	}
	std::vector<unsigned short> levelList = calculateLevelList();
	
	return generateTree(levelList, input);
}

/** Make new packages by combining pairs together */
void PackageMerge::package() {
	size_t index = nodesListPackaged.size();
	
	if (index & 1) { // odd number of elements
		--index; // round to lower even number. Speaking: discard any non pair
		nodesListPackaged.erase(nodesListPackaged.begin()+index); // delete last unpaired element
	}
	
	while (index) {
		index -= 2; // jump through pairwise
		nodesListPackaged[index+1].combine(nodesListPackaged[index]);
		nodesListPackaged.erase(nodesListPackaged.begin()+index);
	}
}

/** Insertion Sort insert for newly found packages and original list */
void PackageMerge::merge() {
	size_t i = 0;
	for (PackageNode opn : nodesListOriginal) {
		while (opn.frequency > nodesListPackaged[i].frequency)
			++i;
		nodesListPackaged.insert(nodesListPackaged.begin() + i, opn);
		++i;
	}
}

/** Level list is needed for tree concatenation */
std::vector<unsigned short> PackageMerge::calculateLevelList() {
	std::map<Symbol, int> levelMap;
	for (PackageNode pn : nodesListPackaged)
		for (Symbol s : pn.symbols)
			levelMap[s] += 1;
	
	std::vector<unsigned short> levelList;
	for (PackageNode on : nodesListOriginal)
		levelList.push_back( levelMap[on.symbols[0]] );
	
	return levelList;
}

// TODO: refactor this method ... or get rid of it
Node* PackageMerge::generateTree(const std::vector<unsigned short>& levelList, const std::vector<Node*> &nodeList) {
	size_t count = levelList.size();
	if (count != nodeList.size()) {
		fputs("Something is wrong. LevelList and NodeList should always be in sync\n", stderr);<commit_msg>reserve vector memory<commit_after>#include "PackageMerge.hpp"
#include <map>

Node* PackageMerge::generate(const std::vector<Node*> &input, unsigned short limit) {
	nodesListOriginal.clear();
	nodesListPackaged.clear();
	nodesListOriginal.reserve(input.size());
	nodesListPackaged.reserve(input.size()*2); // can never be larger than 2*input
	
	for (Node *n : input)
		nodesListOriginal.push_back( PackageNode(n->symbol, n->frequency) );
	
	// start off with the original list and evolve package list with each level
	nodesListPackaged = nodesListOriginal;
	
	for (int i = limit; i > 0; --i) {
		package();
		if (i > 1) // why should we merge in the last step? (just all symbols +1)
			merge();
	}
	std::vector<unsigned short> levelList = calculateLevelList();
	
	return generateTree(levelList, input);
}

/** Make new packages by combining pairs together */
void PackageMerge::package() {
	size_t index = nodesListPackaged.size();
	
	if (index & 1) { // odd number of elements
		--index; // round to lower even number. Speaking: discard any non pair
		nodesListPackaged.erase(nodesListPackaged.begin()+index); // delete last unpaired element
	}
	
	while (index) {
		index -= 2; // jump through pairwise
		nodesListPackaged[index+1].combine(nodesListPackaged[index]);
		nodesListPackaged.erase(nodesListPackaged.begin()+index);
	}
}

/** Insertion Sort insert for newly found packages and original list */
void PackageMerge::merge() {
	size_t i = 0;
	for (PackageNode opn : nodesListOriginal) {
		while (opn.frequency > nodesListPackaged[i].frequency)
			++i;
		nodesListPackaged.insert(nodesListPackaged.begin() + i, opn);
		++i;
	}
}

/** Level list is needed for tree concatenation */
std::vector<unsigned short> PackageMerge::calculateLevelList() {
	std::map<Symbol, int> levelMap;
	for (PackageNode pn : nodesListPackaged)
		for (Symbol s : pn.symbols)
			levelMap[s] += 1;
	
	std::vector<unsigned short> levelList;
	levelList.reserve(nodesListOriginal.size());
	for (PackageNode on : nodesListOriginal)
		levelList.push_back( levelMap[on.symbols[0]] );
	
	return levelList;
}

// TODO: refactor this method ... or get rid of it
Node* PackageMerge::generateTree(const std::vector<unsigned short>& levelList, const std::vector<Node*> &nodeList) {
	size_t count = levelList.size();
	if (count != nodeList.size()) {
		fputs("Something is wrong. LevelList and NodeList should always be in sync\n", stderr);
{'fraction_non_alphanumeric': 0.13036876355748372, 'fraction_numerical': 0.004338394793926247, 'mean_word_length': 4.742216687422167, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 29, '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': '2637672', 'n_tokens_mistral': 1519, 'n_tokens_neox': 1425, 'n_words': 421}