HW#2 Sergei Zherevchuk

[Sergei Zherevchuk]

Здравствуйте!

В huffman.hpp решил ничего не писать, кроме compress/decompress, поскольку посчитал это деталью реализации, хотя у меня самая наивная реализация для мета-информации (256 * 4 байт)

Можно было бы, наверное, сделать публичные методы write_meta, write_encoded_data (и т.д.), чтобы дать другому программисту заменить неэффективную реализацию для чтения/записи дополнительной информации, но я не до конца уверен в этом моменте.

Валидацию аргументов командной строки (кроме кол-ва) не делаю, стоит поменять их порядок или опустить один из них и ничего работать не будет.

[Sergei Zherevchuk]

Видел рекомендацию оборачивать в анонимный namespace детали реализации, но пока не ознакомился как это сделать, постараюсь успеть поправить до проверки.

У меня есть ещё несколько вопросов, буду благодарен комментариям по ним.

Сейчас есть 2 одинаковые функции, отличающиеся только 1 строкой:

• print_huffman_tree
• collect_huffman_codes

Как обычно обобщают такой случай? Передают функцию-обработчик по ссылке?

Дерево у меня состоит из вершин двух видов: leaf, internal. Для внутренних вершин дерева я использую такой код:

HuffmanTreeNode * parent = new HuffmanTreeNode(0, left->byte_frequency + right->byte_frequency, left, right);

Где 0 - это фейковое значение для внутреннего узла дерева. Как грамотнее поступить с таким кодом? Создать отдельный конструктор и скрыть фейковое значение там? Создать отдельный класс вершины?

Есть такие включения:

#include <queue>
#include <vector>

Если queue включает vector (содержит #include <vector>), то его хедеры тоже будут включены неявно? Clion сейчас ругается, что vector - unused import statement, пытаюсь понять, почему он ругается. И мне ведь всё равно явно надо включать все заголовки?

Не до конца понимаю цитаты из общих рекомендаций.

Если у класса есть открытые поля, то все ее поля должны быть открытыми. В таких классах из методов допускается только конструкторы и операторы.

Т.е. нельзя создать вспомогательный метод? Например, как у меня метод is_leaf у вершины дерева. Или это относится только к классу, но не структуре?

Фигурные скобки всегда начинаются и заканчиваются на отдельных строках

А как быть, если тело блока пустое? Всё равно на разных строках? Например, конструктор пустой.

[Vladimir Rutsky]

В huffman.hpp решил ничего не писать, кроме compress/decompress, поскольку посчитал это деталью реализации, хотя у меня самая наивная реализация для мета-информации (256 * 4 байт)
Можно было бы, наверное, сделать публичные методы write_meta, write_encoded_data (и т.д.), чтобы дать другому программисту заменить неэффективную реализацию для чтения/записи дополнительной информации, но я не до конца уверен в этом моменте.

Да, это возможное место расширение API вашего решения, но оно не требуется и не так тривиально --- недостаточно вынести эти функции в заголовочный файл, нужно ещё предоставить средство для их подмены (передавать соответствующий функтор или интерфейс в сжатие/распаковку, например).

Валидацию аргументов командной строки (кроме кол-ва) не делаю, стоит поменять их порядок или опустить один из них и ничего работать не будет.

Зафиксировать порядок аргументов допустимо в данной задаче (но проверку количества аргументов и точное равенство аргументов ожидаемым опциям всё равно необходимо производить).

Видел рекомендацию оборачивать в анонимный namespace детали реализации, но пока не ознакомился как это сделать, постараюсь успеть поправить до проверки.

Сейчас функции внутри huffman.cpp имеют внешнюю линковку (по умолчанию). Если вы (или пользователь ваших huffman.hpp/huffman.cpp) случайно создат также с внешней линковкой, например, функцию std::vector<uint32_t> read_meta(std::ifstream & ), то возникнет ошибка линковки.

Чтобы этого избежать стоит делать функции-детали реализации в cpp файле static или помещать их в namespace { std::vector<uint32_t> read_meta(std::ifstream & ) { ... } } (анонимный namespace).

У меня есть ещё несколько вопросов, буду благодарен комментариям по ним.

1. Сейчас есть 2 одинаковые функции, отличающиеся только 1 строкой:

• print_huffman_tree
• collect_huffman_codes

Как обычно обобщают такой случай? Передают функцию-обработчик по ссылке?

Да, обычно реализуют какое-то подобие ​Visitor pattern. Например, реализовав функцию void visit_tree(std::function<void(const HuffmanTreeNode * node, const std::string & acc)> &).

2. Дерево у меня состоит из вершин двух видов: leaf, internal. Для внутренних вершин дерева я использую такой код:

   HuffmanTreeNode * parent = new HuffmanTreeNode(0, left->byte_frequency + right->byte_frequency, left, right);
   

Где 0 - это фейковое значение для внутреннего узла дерева. Как грамотнее поступить с таким кодом? Создать отдельный конструктор и скрыть фейковое значение там? Создать отдельный класс вершины?

Создание нового класса усложнит реализацию и практически ничего не даст, я не рекомендую здесь так делать.
Можно сделать два конструктора, да: один для leaf, один для internal.

3. Есть такие включения:

   #include <queue>
   #include <vector>
   

Если queue включает vector (содержит #include <vector>), то его хедеры тоже будут включены неявно? > Clion сейчас ругается, что vector - unused import statement, пытаюсь понять, почему он ругается. И мне ведь всё равно явно надо включать все заголовки?

То, что Clion выдаёт такое предупреждение любопытно. Для меня не очевидно, что включение <queue> всегда включит <vector> в соответствии со Стандартом языка. Возможно Clion знает, что где-то есть такая гарантия.

4. Не до конца понимаю цитаты из общих рекомендаций.

   Если у класса есть открытые поля, то все ее поля должны быть открытыми. В таких классах из методов допускается только конструкторы и операторы.
   

Т.е. нельзя создать вспомогательный метод? Например, как у меня метод is_leaf у вершины дерева. Или это относится только к классу, но не структуре?

Насколько я понимаю, здесь предполагается разделение на классы-структуры (например class Color {public: uint8_t r, g, b;}) и классы-объекты (которые имеют нетривиальное состояние и поведение). Обычно у классов-объектов все изменения проиcходят через методы, т.к. в противном случае класс не сможет просто отследить, что кто-то поменял его состояние.

Я не согласен с тем, что данная рекомендация применима здесь. По крайней мере она требует уточнения.
Возможно, имелось в виду, что если можно реализовать метод внешним, то его стоит сделать внешним и следовало сделать is_leaf и get_child внешними функциями, но на мой взгляд это не оправдано в данном случае.

Фигурные скобки всегда начинаются и заканчиваются на отдельных строках

А как быть, если тело блока пустое? Всё равно на разных строках? Например, конструктор пустой.

Нет, думаю всё-таки стоит оставить скобки на одной строке в таком случае.

Замечания:

1. Вы выводите количество элементов в таблице частот (256), а не размер, которая она занимает в файле (256 * 4).

2. Т.к. вы используете std::vector для таблицы частот, вы можете сериализовать и десериализовать её как единый блок памяти:

output_file.write(reinterpret_cast<char *>(byte_frequency.data()), sizeof(byte_frequency[0]) * byte_frequency.size());

3. Используйте size_t для индексов массивов.

4. Используйте стабильный компаратор в std::priority_queue. std::priority_queue не гарантирует порядок в котором элементы с одним и тем же приоритетом будут извлечены --- при сжатии порядок может оказаться одним, а при разжатии другим.

Вы сдаёте к дедлайну, но я не могу зачесть ваше решение в таком виде.
Исправьте, пожалуйста, в ближайшее время, и я зачту его с минусом.

[Sergei Zherevchuk]

Большое спасибо за замечания!
Исправления внёс.

[Vladimir Rutsky]

Сергей, для не-листьев byte_value всегда нулевой --- компаратор не даёт детерминированного порядка.
Исправьте, пожалуйста.

[Sergei Zherevchuk]

Астрологи объявили неделю невнимательности. :| Поторопился. Ещё и уведомление пропустил, извиняюсь.

Ввёл глобальный счетчик для вершин. Кажется, что можно было счётчик держать прямо в функции build_huffman_tree. А я ведь правильно понимаю, что если мы прячем детали реализации за анонимным неймспейсом, то при сборке программы мы уже не имеем какой-либо возможности перемешать экземпляры той же структуры HuffmanTreeNode? из разных единиц трансляции? Например, каким-то способом поместить их в одну очередь.

[Vladimir Rutsky]

А я ведь правильно понимаю, что если мы прячем детали реализации за анонимным неймспейсом, то при сборке программы мы уже не имеем какой-либо возможности перемешать экземпляры той же структуры HuffmanTreeNode? из разных единиц трансляции?
Например, каким-то способом поместить их в одну очередь.

Не понял вопроса. Анонимный namespace гарантирует, что не будет коллизии имён. Вы в принципе можете передавать экземпляры класса между единицами трансляции, но т.к. тип известен только в одной из них это не очень полезно (да и не предполагается, анонимные namespace как раз для приватных вещей, которые не должны быть использованы в других модулях).
Пример про очередь не понял.

Замечания:

1. const std::size_t get_id() const { первый const здесь лишний.

2. Вместо глобального счетчика лучше использовать локальный, или обойтись без счетчика, например, присваивая в узел не-лист минимальный символ из поддеревьев. Глобальный счетчик может переполнится, он делает программу автоматически небезопасной для использования из нескольких потоков, и т.п.

Решение зачтено. С минусом, как я указывал выше.

[Sergei Zherevchuk]

Точно! Такое красивое решение и не пришло в голову. Проблему с глобальным счётчиком осознаю, но ничего умнее в голову не пришло в тот момент.
Спасибо!
P.S. Непонятный вопрос переадресую своему знакомому, пока плохо понимаю как его сформулировать грамотно.