<commit_before>#include "node.hpp"
#include <set>
#include <fstream>
#include <queue>
#include <functional>


#ifndef HUFFMAN_TREE_HPP
#define HUFFMAN_TREE_HPP

namespace cpr
{
	namespace huffman
	{
		template<typename Char, typename Freq>
		class HuffmanTree
		{
		public:
			using SharedNode = Node<Char, Freq>::SharedNode;

			//template<typename Container>
			//explicit HuffmanTree(Container const& nodes)
			//	: root_{ make_tree(nodes) }
			//{	}

		private:
			SharedNode root_;

			//template<typename Container>
			//SharedNode make_tree(Container const& nodes) const
			//{
			//	auto greater = [](SharedNode lhs, SharedNode rhs){return lhs->freq_ > rhs->freq_; };
			//	using MinPriorityQueue = std::priority_queue < SharedNode, std::vector<SharedNode>>, decltype(greater) > ;

			//	MinPriorityQueue queue(greater);
			//	for (auto const& n : node)
			//		queue.push(make_new_node(n));

			//	for (int _ = 1; _ != container.size(); ++_)
			//	{
			//		auto z = make_new_node();
			//		z->left_ = make_new_node(queue.top());
			//		queue.pop();
			//		z->right_ = make_new_node(queue.top());
			//		queue.pop();
			//		z.freq_ = z.left_->freq_ + z.right_->freq_;
			//		queue.push(z);
			//	}
			//}
		};
	}
}

#endif // !HUFFMAN_TREE_HPP<commit_msg>changed to use std map as frequency map<commit_after>#include "node.hpp"
#include <set>
#include <map>
#include <fstream>
#include <queue>
#include <functional>


#ifndef HUFFMAN_TREE_HPP
#define HUFFMAN_TREE_HPP

namespace cpr
{
	namespace huffman
	{
		template<typename Char, typename Freq>
		class HuffmanTree
		{
		public:
			using SharedNode = Node<Char, Freq>::SharedNode;
			using FrequencyMap = std::map < Char, Freq > ;

			explicit HuffmanTree(FrequencyMap const& map)
				: root_{make_tree(map)}
			{}

		private:
			SharedNode root_;

			// huffman coding algorithm 
			// based on a pseudocode on 16.3 CLRS 3rd.
			SharedNode make_tree(FrequencyMap const& map) const
			{
					auto greater = [](SharedNode lhs, SharedNode rhs){return lhs->freq_ > rhs->freq_; };
					using MinPriorityQueue = std::priority_queue < SharedNode, std::vector<SharedNode>>, decltype(greater) > ;

					MinPriorityQueue queue(greater);
					for (auto const& pair : map)
						queue.push(make_new_node(pair.first, pair.second));
					
					for (int count = 1; count != map.size(); ++count)
					{
						auto merge = make_new_node<Char, Freq>();
						merge->left_ = make_new_node(*queue.top());
						queue.pop();
						merge->right_ = make_new_node(*queue.top());
						queue.pop();
						merge.freq_ = merge.left_->freq_ + merge.right_->freq_;
						queue.push(merge);
					}

					return queue.top();
			}
		};
	}
}

#endif // !HUFFMAN_TREE_HPP
{'fraction_non_alphanumeric': 0.14825796886582654, 'fraction_numerical': 0.002223869532987398, 'mean_word_length': 3.2171875, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 40, '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': '897409', 'n_tokens_mistral': 1147, 'n_tokens_neox': 940, 'n_words': 202}