Добавлена первая задача пятой главы

6 files changed, 478 insertions, 5 deletions

diff --git a/Занимательное программирование/5/1_huffman/.gitignore b/Занимательное программирование/5/1_huffman/.gitignore
new file mode 100644
index 0000000..9c9f9d4
--- /dev/null
+++ b/Занимательное программирование/5/1_huffman/.gitignore
@@ -0,0 +1,2 @@
+.ninja_log
+build/
diff --git a/Занимательное программирование/5/1_huffman/build.ninja b/Занимательное программирование/5/1_huffman/build.ninja
new file mode 100644
index 0000000..e8581f8
--- /dev/null
+++ b/Занимательное программирование/5/1_huffman/build.ninja
@@ -0,0 +1,12 @@
+cxxflags =
+
+rule cxx
+  command = g++ $cxxflags -c -o $out $in
+
+rule ld
+  command = g++ $cxxflags $in -o $out
+
+build build/huffman.o: cxx huffman.cpp | huffman.hpp
+build build/huffman: ld main.cpp build/huffman.o
+
+default build/huffman
diff --git a/Занимательное программирование/5/1_huffman/huffman.cpp b/Занимательное программирование/5/1_huffman/huffman.cpp
new file mode 100644
index 0000000..c518002
--- /dev/null
+++ b/Занимательное программирование/5/1_huffman/huffman.cpp
@@ -0,0 +1,320 @@
+#include <array>
+#include <cstdint>
+#include <iostream>
+#include <vector>
+#include <memory>
+#include <string>
+#include <algorithm>
+#include <bitset>
+#include "huffman.hpp"
+#include <arpa/inet.h>
+
+huffman_tree::huffman_tree(const std::string& value)
+    : _value(value), _left(nullptr), _right(nullptr)
+{
+}
+
+huffman_tree::huffman_tree(std::shared_ptr<huffman_tree> left, std::shared_ptr<huffman_tree> right)
+    : _value(""), _left(left), _right(right)
+{
+}
+
+std::uint8_t huffman_tree::value() const
+{
+    return _value.front();
+}
+
+std::shared_ptr<huffman_tree> huffman_tree::left() const
+{
+    return _left;
+}
+
+std::shared_ptr<huffman_tree> huffman_tree::right() const
+{
+    return _right;
+}
+
+bool huffman_tree::is_leaf() const
+{
+    return !(this->left() || this->right());
+}
+
+huffman_probability::huffman_probability(const std::string& bytes, double probability)
+        : bytes(bytes), probability(probability), tree(std::make_shared<huffman_tree>(bytes))
+    {
+    }
+
+huffman_probability huffman_probability::operator+(const huffman_probability& that) const
+{
+    huffman_probability result{ this->bytes + that.bytes, this->probability + that.probability };
+    result.tree = std::make_shared<huffman_tree>(this->tree, that.tree);
+
+    return result;
+}
+
+bool huffman_probability::operator<(const huffman_probability& that) const
+{
+    return this->probability < that.probability;
+}
+
+bool huffman_probability::operator>(const huffman_probability& that) const
+{
+    return this->probability > that.probability;
+}
+
+bool huffman_probability::operator<=(const huffman_probability& that) const
+{
+    return this->probability <= that.probability;
+}
+
+bool huffman_probability::operator>=(const huffman_probability& that) const
+{
+    return this->probability >= that.probability;
+}
+
+std::pair<std::bitset<8>, std::size_t> encode_coding(const coding& input, std::ostream& output,
+        std::bitset<8> bitset, std::size_t index)
+{
+    for (const bool bit: input)
+    {
+        bitset[index] = bit;
+
+        if (index == 7)
+        {
+            output.put(static_cast<std::ostream::char_type>(bitset.to_ulong()));
+            index = 0;
+            bitset = std::bitset<8>();
+        }
+        else
+        {
+            ++index;
+        }
+    }
+    return { bitset, index };
+}
+
+void huffman_table::create_table(std::shared_ptr<huffman_tree> tree, coding path)
+{
+    if (tree->is_leaf())
+    {
+        insert(tree->value(), std::move(path));
+    }
+    else
+    {
+        coding new_path;
+
+        new_path = path;
+        new_path.push_back(false);
+        create_table(tree->left(), std::move(new_path));
+
+        new_path = path;
+        new_path.push_back(true);
+        create_table(tree->right(), std::move(new_path));
+    }
+}
+
+huffman_table::huffman_table(std::shared_ptr<huffman_tree> tree)
+{
+    create_table(tree, coding());
+}
+
+huffman_table::huffman_table(std::vector<std::uint8_t>::const_iterator& coding_stream)
+{
+    std::size_t table_size = *coding_stream;
+
+    std::advance(coding_stream, 1);
+
+    for (std::uint8_t i = 0; i < table_size; ++i)
+    {
+        auto coded_symbol = static_cast<std::byte>(*coding_stream);
+
+        std::advance(coding_stream, 1);
+        std::uint8_t bits_in_coding = *coding_stream;
+
+        std::advance(coding_stream, 1);
+        coding current_coding;
+        std::size_t current_bit{ 0 };
+
+        for (std::uint8_t j = 0; j < bits_in_coding; ++j)
+        {
+            std::bitset<8> current_bitset{ *coding_stream };
+
+            current_coding.push_back(current_bitset[current_bit]);
+
+            if (current_bit == 7)
+            {
+                current_bit = 0;
+                std::advance(coding_stream, 1);
+            }
+            else
+            {
+                ++current_bit;
+            }
+        }
+        if (current_bit != 0)
+        {
+            std::advance(coding_stream, 1);
+        }
+        this->payload.insert({ coded_symbol, current_coding });
+    }
+}
+
+void huffman_table::insert(std::uint8_t byte, coding&& path)
+{
+    this->payload.insert({ static_cast<std::byte>(byte), std::move(path) });
+}
+
+const coding& huffman_table::operator[](std::uint8_t byte) const
+{
+    return this->payload.at(static_cast<std::byte>(byte));
+}
+
+std::size_t huffman_table::size() const
+{
+    return this->payload.size();
+}
+
+void huffman_table::encode(std::ostream& output) const
+{
+    // The first byte is the table size.
+    output.put(static_cast<std::ostream::char_type>(size()));
+
+    for (const std::pair<std::byte, coding>& entry: this->payload)
+    {
+        // For each entry write the byte encoded.
+        output.put(static_cast<std::ostream::char_type>(entry.first));
+        output.put(static_cast<std::ostream::char_type>(entry.second.size()));
+
+        auto rest = encode_coding(entry.second, output, {}, 0);
+        if (rest.second > 0)
+        {
+            output << static_cast<std::ostream::char_type>(rest.first.to_ulong());
+        }
+    }
+}
+
+std::unordered_map<std::byte, coding>::iterator huffman_table::begin()
+{
+    return this->payload.begin();
+}
+
+std::unordered_map<std::byte, coding>::iterator huffman_table::end()
+{
+    return this->payload.end();
+}
+
+std::unordered_map<std::byte, coding>::const_iterator huffman_table::begin() const
+{
+    return this->payload.cbegin();
+}
+
+std::unordered_map<std::byte, coding>::const_iterator huffman_table::end() const
+{
+    return this->payload.cend();
+}
+
+std::shared_ptr<huffman_tree> create_tree(probability_list& probabilities)
+{
+    while (probabilities.size() > 1)
+    {
+        std::sort(std::begin(probabilities), std::end(probabilities), std::greater());
+        auto last = probabilities.back();
+
+        probabilities.pop_back();
+        probabilities.back() = probabilities.back() + last;
+    }
+    return probabilities.front().tree;
+}
+
+probability_list adapt_probabilities(const std::vector<std::uint8_t>& input)
+{
+    std::array<std::size_t, 256> counts = {};
+    probability_list result;
+
+    for (auto byte: input)
+    {
+        ++counts[byte];
+    }
+    for (std::array<std::size_t, 256>::const_iterator count = std::cbegin(counts); count != std::cend(counts); ++count)
+    {
+        if (*count > 0)
+        {
+            result.push_back({
+                    std::string(1, static_cast<char>(std::distance(std::cbegin(counts), count))),
+                    *count / 256.0
+            });
+        }
+    }
+    return result;
+}
+
+void encode(const huffman_table& table, const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    std::pair<std::bitset<8>, std::size_t> rest{ {}, 0 };
+    auto input_size = htonl(input.size());
+
+    // Write the number of elements.
+    output.write(reinterpret_cast<const char *>(&input_size), 4);
+
+    table.encode(output);
+    for (const std::uint8_t character: input)
+    {
+        rest = encode_coding(table[character], output, rest.first, rest.second);
+    }
+    if (rest.second > 0)
+    {
+        output << static_cast<std::ostream::char_type>(rest.first.to_ulong());
+    }
+}
+
+void compress(const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    probability_list probabilities = adapt_probabilities(input);
+    std::shared_ptr<huffman_tree> tree = create_tree(probabilities);
+    huffman_table table{ tree };
+
+    encode(table, input, output);
+}
+
+void decompress(const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    auto input_size = ntohl(*reinterpret_cast<const std::uint32_t *>(input.data()));
+    auto table_iterator = std::cbegin(input) + 4;
+    huffman_table table{ table_iterator };
+    std::unordered_map<coding, std::byte> reverse_table;
+
+    for (auto entry: table)
+    {
+        reverse_table.insert({ entry.second, entry.first });
+    }
+    std::vector<bool> bit_input;
+    std::size_t element_count{ 0 };
+
+    while (table_iterator != std::cend(input))
+    {
+        std::bitset<8> current_bitset{ *table_iterator };
+
+        for (auto j = 0; j < current_bitset.size(); ++j)
+        {
+            bit_input.push_back(current_bitset[j]);
+            auto lookup_result = reverse_table.find(bit_input);
+
+            if (lookup_result != std::cend(reverse_table))
+            {
+                output << static_cast<unsigned char>(lookup_result->second);
+                bit_input.clear();
+                if (++element_count == input_size)
+                {
+                    break;
+                }
+            }
+        }
+
+        std::advance(table_iterator, 1);
+    }
+/*
+        << "Input size: " << input_size << std::endl
+        << "Table size: " << static_cast<unsigned int>(input.at(4)) << std::endl;
+
+*/
+}
diff --git a/Занимательное программирование/5/1_huffman/huffman.hpp b/Занимательное программирование/5/1_huffman/huffman.hpp
new file mode 100644
index 0000000..6e297f0
--- /dev/null
+++ b/Занимательное программирование/5/1_huffman/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);
diff --git a/Занимательное программирование/5/1_huffman/main.cpp b/Занимательное программирование/5/1_huffman/main.cpp
new file mode 100644
index 0000000..24aba2c
--- /dev/null
+++ b/Занимательное программирование/5/1_huffman/main.cpp
@@ -0,0 +1,69 @@
+#include <cstring>
+#include <fstream>
+#include <vector>
+#include <cstdint>
+#include <iostream>
+#include "huffman.hpp"
+
+std::vector<std::uint8_t> read_file(char *filename)
+{
+    std::ifstream input_file{ filename, std::ios::binary | std::ios::in };
+    input_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    return std::vector<std::uint8_t>{ std::istreambuf_iterator<char>(input_file), {} };
+}
+
+enum class direction {
+    compress,
+    decompress
+};
+
+int show_usage()
+{
+    std::cerr << "Usage: huffman (compress|decompress) input_file output_file." << std::endl;
+    return 1;
+}
+
+int main(int argc, char **argv)
+{
+    direction operation;
+    if (argc != 4)
+    {
+        return show_usage();
+    }
+    if (std::strcmp(argv[1], "compress") == 0)
+    {
+        operation = direction::compress;
+    }
+    else if (std::strcmp(argv[1], "decompress") == 0)
+    {
+        operation = direction::decompress;
+    }
+    else
+    {
+        return show_usage();
+    }
+    std::vector<std::uint8_t> input;
+    try
+    {
+        input = read_file(argv[2]);
+    }
+    catch (std::iostream::failure& exception)
+    {
+        std::cerr << "Error opening file \"" << argv[2] << "\" for reading." << std::endl;
+        return 2;
+    }
+    std::ofstream output_file{ argv[3], std::ios::binary | std::ios::out | std::ios::trunc };
+    output_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    switch (operation)
+    {
+    case direction::compress:
+        compress(input, output_file);
+        break;
+    case direction::decompress:
+        decompress(input, output_file);
+        break;
+    }
+    return 0;
+}
diff --git a/Занимательное программирование/README.txt b/Занимательное программирование/README.txt
index 2b03ec7..d32d63a 100644
--- a/Занимательное программирование/README.txt
+++ b/Занимательное программирование/README.txt
@@ -1,11 +1,12 @@
-Задания решены на разных языках программирования, но в большинстве
-случаев используется язык, выбранный для примеров и в самой книге,
-Pascal или Delphi, в моем случае это Free Pascal и Lazarus.
+Задания решены на разных языках программирования.
 
 В первой главе ("Компьютерное моделирование") есть один С файл (для
-рисования применяется Cairo).
+рисования применяется Cairo), остальные задачи сделаны в Pascal и
+Lazarus.
 
 Вторая глава ("Анимация и графические эффекты") основывается на Java и
 игровом движке libGDX.
 
-Четвертая глава ("Трехмерная графика") сделана с Pascal и libGDX.
+Третья глава ("Трехмерная графика") решена в Lazarus.
+
+Четвертая глава ("Лабиринты") сделана с Pascal и libGDX.