From 82ae29cb8a59a1e093190d14f8c5097658545a12 Mon Sep 17 00:00:00 2001
From: Eugen Wissner <belka@caraus.de>
Date: Fri, 13 Feb 2026 22:03:01 +0100
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D0=B2=D1=82=D0=BE=D1=80=D0=B0=D1=8F=20=D0=B7=D0=B0=D0=B4?=
 =?UTF-8?q?=D0=B0=D1=87=D0=B0=20=D0=BF=D1=8F=D1=82=D0=BE=D0=B9=20=D0=B3?=
 =?UTF-8?q?=D0=BB=D0=B0=D0=B2=D1=8B?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 .../5/2_grey/huffman.hpp"                          | 69 ++++++++++++++++++++++
 1 file changed, 69 insertions(+)
 create mode 100644 "\320\227\320\260\320\275\320\270\320\274\320\260\321\202\320\265\320\273\321\214\320\275\320\276\320\265 \320\277\321\200\320\276\320\263\321\200\320\260\320\274\320\274\320\270\321\200\320\276\320\262\320\260\320\275\320\270\320\265/5/2_grey/huffman.hpp"

(limited to 'Занимательное программирование/5/2_grey/huffman.hpp')

diff --git "a/\320\227\320\260\320\275\320\270\320\274\320\260\321\202\320\265\320\273\321\214\320\275\320\276\320\265 \320\277\321\200\320\276\320\263\321\200\320\260\320\274\320\274\320\270\321\200\320\276\320\262\320\260\320\275\320\270\320\265/5/2_grey/huffman.hpp" "b/\320\227\320\260\320\275\320\270\320\274\320\260\321\202\320\265\320\273\321\214\320\275\320\276\320\265 \320\277\321\200\320\276\320\263\321\200\320\260\320\274\320\274\320\270\321\200\320\276\320\262\320\260\320\275\320\270\320\265/5/2_grey/huffman.hpp"
new file mode 100644
index 0000000..6e297f0
--- /dev/null
+++ "b/\320\227\320\260\320\275\320\270\320\274\320\260\321\202\320\265\320\273\321\214\320\275\320\276\320\265 \320\277\321\200\320\276\320\263\321\200\320\260\320\274\320\274\320\270\321\200\320\276\320\262\320\260\320\275\320\270\320\265/5/2_grey/huffman.hpp"	
@@ -0,0 +1,69 @@
+#include <string>
+#include <memory>
+#include <vector>
+#include <unordered_map>
+#include <cstdint>
+
+class huffman_tree
+{
+    std::string _value;
+    std::shared_ptr<huffman_tree> _left;
+    std::shared_ptr<huffman_tree> _right;
+
+public:
+    huffman_tree(const std::string& value);
+    huffman_tree(std::shared_ptr<huffman_tree> left, std::shared_ptr<huffman_tree> right);
+
+    std::uint8_t value() const;
+    std::shared_ptr<huffman_tree> left() const;
+    std::shared_ptr<huffman_tree> right() const;
+
+    bool is_leaf() const;
+};
+
+struct huffman_probability
+{
+    std::string bytes;
+    double probability;
+    std::shared_ptr<huffman_tree> tree;
+
+    huffman_probability(const std::string& bytes, double probability);
+
+    huffman_probability operator+(const huffman_probability& that) const;
+    bool operator<(const huffman_probability& that) const;
+    bool operator>(const huffman_probability& that) const;
+    bool operator<=(const huffman_probability& that) const;
+    bool operator>=(const huffman_probability& that) const;
+};
+
+using coding = std::vector<bool>;
+using probability_list = std::vector<huffman_probability>;
+using probability_iterator = probability_list::iterator;
+using probability_const_iterator = probability_list::const_iterator;
+
+class huffman_table
+{
+    std::unordered_map<std::byte, coding> payload;
+
+    void create_table(std::shared_ptr<huffman_tree> tree, coding path);
+
+public:
+    huffman_table(std::shared_ptr<huffman_tree> tree);
+    huffman_table(std::vector<std::uint8_t>::const_iterator& coding_stream);
+    huffman_table() = default;
+
+    void insert(std::uint8_t byte, coding&& path);
+    void encode(std::ostream& output) const;
+    std::size_t size() const;
+    std::unordered_map<std::byte, coding>::iterator begin();
+    std::unordered_map<std::byte, coding>::iterator end();
+    std::unordered_map<std::byte, coding>::const_iterator begin() const;
+    std::unordered_map<std::byte, coding>::const_iterator end() const;
+
+    const coding& operator[](std::uint8_t byte) const;
+};
+
+std::shared_ptr<huffman_tree> create_tree(probability_list& probabilities);
+probability_list adapt_probabilities(const std::vector<std::uint8_t>& input);
+void compress(const std::vector<std::uint8_t>& input, std::ostream& output);
+void decompress(const std::vector<std::uint8_t>& input, std::ostream& output);
-- 
cgit v1.2.3