HW #3

[Egor Suvorov]

Как обсудили в личке: пока не проверяю, потому что обновилось условие. Чтобы первую попытку не тратить.

Как будете готовы — поменяйте обратно на "ожидается проверка".

[Egor Suvorov]

Проверялась ревизия 3856.

Корректность 8/9.

• Беда с компиляцией. На самом деле, с предупреждениями, поэтому это в стиль.

  /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/src/Huffman.cpp:24:16: error: moving a temporary object prevents copy elision [-Werror,-Wpessimizing-move]
          root = std::move(heap.extractMin());
                 ^
  /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/src/Huffman.cpp:24:16: note: remove std::move call here
          root = std::move(heap.extractMin());
                 ^~~~~~~~~~                 ~
  In file included from /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/src/Huffman.cpp:3:
  In file included from /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/include/Huffman.h:7:
  /usr/lib/llvm-10/bin/../include/c++/v1/set:1127:30: error: the specified comparator type does not provide a viable const call operator [-Werror,-Wuser-defined-warnings]
          static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
                               ^
  /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/include/Huffman.h:57:7: note: in instantiation of member function 'std::__1::multiset<std::__1::unique_ptr<Huffman::Tree::Node, std::__1::default_delete<Huffman::Tree::Node> >, Huffman::Tree::Node::Compare, std::__1::allocator<std::__1::unique_ptr<Huffman::Tree::Node, std::__1::default_delete<Huffman::Tree::Node> > > >::~multiset' requested here
  class NodeHeap final {
        ^
  /usr/lib/llvm-10/bin/../include/c++/v1/__tree:976:5: note: from 'diagnose_if' attribute on '__diagnose_non_const_comparator<std::__1::unique_ptr<Huffman::Tree::Node, std::__1::default_delete<Huffman::Tree::Node> >, Huffman::Tree::Node::Compare>':
      _LIBCPP_DIAGNOSE_WARNING(!std::__invokable<_Compare const&, _Tp const&, _Tp const&>::value,
      ^                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  /usr/lib/llvm-10/bin/../include/c++/v1/__config:1297:21: note: expanded from macro '_LIBCPP_DIAGNOSE_WARNING'
       __attribute__((diagnose_if(__VA_ARGS__, "warning")))
                      ^           ~~~~~~~~~~~
  2 errors generated.
  

Потом:

In file included from /home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/src/HuffmanArchiver.cpp:4:
/home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/include/HuffmanArchiver.h:22:1: error: 'Statistics' defined as a struct here but previously declared as a class; this is valid, but may result in linker errors under the Microsoft C++ ABI [-Werror,-Wmismatched-tags]
struct Statistics final {
^
/home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/include/HuffmanArchiver.h:8:1: note: did you mean struct here?
class Statistics;
^~~~~
struct
1 error generated.

Потом:

/home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/test/TestHuffman.cpp:21:28: error: moving a temporary object prevents copy elision [-Werror,-Wpessimizing-move]
        NodePointer node = std::move(std::make_unique<Node>(std::move(left), std::move(right)));
                           ^
/home/osboxes/cpp2019/cpp19/karnaukhov.kirill/hw_03/test/TestHuffman.cpp:21:28: note: remove std::move call here
        NodePointer node = std::move(std::make_unique<Node>(std::move(left), std::move(right)));
                           ^~~~~~~~~~                                                         ~
1 error generated.

Потом [нашёлся баг](​https://github.com/onqtam/doctest/issues/356) то ли в doctest, то ли в стандартной библиотеке, но это уже не ваша проблема :)

• Не сошёлся вывод: сумма дополнительных данных и сжатых не равна итоговому размеру сжатого файла. Почти на всех тестах, причём на некоторых довольно большое расхождение.

Тесты 6/8

• Совершенно лишние try/catch. Если вылетит исключение, doctest его сам поймает и красиво упадёт, а чтобы ожидать исключение, есть специальные команды.
• Лучше не хардкодить размеры массивов для Flags, а вычислять их через std::size
• TestHuffmanCode.cpp надо разделить на мелкие тесты.
• В checkTextEndToEnd можно и размеры данных до/после в байтах. Как раз для корректности нужно. И размеры получившегося архива тоже лучше проверить. А вдруг не сжимает?
• Вместо getRandomUInt и своих велосипедов используйте uniform_int_distribution.
• Стоит протестировать точные длины кодов, которые создаёт Tree. И даже их значения.

Архитектура 3/5

• Если произошла ошибка, следует завершать программу с ненулевым кодом возврата.
• Непонятно, с чего бы конструктор Flags принимает size_t, хотя исходно был int. И вообще тут прекрасно подойдёт какой-нибудь vector<string_view>, если уж на то пошло.
• CLIException — унаследуйтесь лучше от runtime_error/logic_error
• numberOfBytes а) нужен только для подсчёта статистики архиватором — лучше смотреть на количество выведенных байт; б) находится в HuffmanCode.h не по делу, это вообще приватная функция для HuffmanArchiver.cpp
• Code::getByte() как-то молча обрезает код по восьми битам. Заглушение ошибок, плохо.
• Вообще не понял, зачем нужен Code, когда это просто обёртка на deque<bool>/vector<bool>. Любой из них прекрасно подойдёт и по типам, и по семантике, казалось бы. Разве что getByte() придётся отдельно написать, но это, имхо, и к лучшему — будет явно везде написано, что да, мы действительно берём только первые восемь бит. Сейчас это всё равно не "код Хаффмана" — вы его также используете и для записи целых байт в поток.
• Не стоит завязываться на размер size_t, особенно если вы претендуете на кроссплатформенность, не завязываясь на endianness.
• Очень странно, что потребовался getNextByte у битового потока. Он же нужен только для сжатия данных. А вы читаете и в обход потока, см readUInt. Лучше как-то чётко разделить.
• stats вы везде считаете руками. Лучше это делать автоматически, посмотрев на позиции внутри потоков.
• >> — странное обозначение для операции "считай байты и посчитай частоты". Я бы ожидал, что это именно чтение таблицы частот в каком-то виде.
• Незачем записывать длину кодируемой последовательности в битах. Её ещё и считать муторно.
• Хорошо бы вызывать padToByte() в деструкторе, чтобы нельзя было случайно недозаписать данные. Или лучше — проверять, что он был вызван.
• Надо разделить "бор" и "итератор по бору".
• Не может ли Node быть вообще приватной для Trie структурой?
• Файл Huffman.h содержит дерево, вершины, кучу вершин (которая вообще деталь реализации алгоритма, равно как и Node::Compare, не должны торчать из .cpp) — как-то не очень название файла.
• HuffmanTrie ничего специфичного для Хаффмана не имеет.
• getAllCodes() должен возвращать вектор. Иначе неясна семантика в случае, когда в codes уже кто-то есть.
• Так ли уж таблице частот надо читать не напрямую из istream, а через IO::?

Стиль 5/8

• Flags — скорее уже как раз не флаги, а полноценные настройки архиватора. От флагов создаютсяю
• CLIException на самом деле может возникнуть только при парсинге аргументов. Лучше так и назвать.
• checkCompleteness() — isComplete().
• Lack of arguments. --> Not enough arguments specified.
• Смотри предупреждения компилятора выше.
• CLI.cpp:69 — лишние скобочки.
• BYTESIZE --> стандартный CHAR_BIT и можно static_assert на его значение.
• Конструктор Code::Code можно сделать при помощи конструктора от двух итераторов, copy или чего-то такого.
• padToByte() у писателя --> flush()
• padToByte() у читателя --> skipUntilByte()
• Не надо сбрасывать буфер в operator<<(ostream&, const Statistics&)
• HuffmanArchiver.cpp:27 — лишние скобки. И вообще это лучше посчитать не руками. а через std::count_if.
• extract/compress — лучше чтобы соответствовали терминам из задания.
• В Archiver::extract [мойте тарелки перед едой](​http://blog.algoprog.ru/init-not-clear/).
• Huffman.cpp:19 — лишняя промежуточная переменная
• Вместо x == nullptr лучше !x

[Egor Suvorov]

А ещё напоминаю про расстановку noexcept и final.

[Карнаухов Кирилл]

• Мне кажется x != nullptr более читабельно, чем !x.
• extract/compress — такие термины использованы в задании.
• Публичная функция getAllCodes(...) и так возвращает вектор. Однако приватная принимает вектор по ссылке для удобной реализации.

[Egor Suvorov]

Very nice. Третья попытка разблокирована.

Корректность 9/9

Тесты 7/8

• Bits
  • Тесты на свойства — это хорошо, но вы так проверите лишь внутреннюю консистентность. Добавьте несколько тестов, которые проверяют, что вы порядок не перепутали, крайние случаи работают...
• TestFrequencyTable
  • Проверьте всё-таки все значения, а не выборочно. Пусть тест будет полным.
• TestHuffmanTree
  • Лучше проверьте ещё и сами коды, не только длины. Алгоритм-то однозначный.
  • Не стоит завязываться на корректность readAndCount. А если уж и завязываетесь (тоже можно), то хотя бы символы отсортируйте, чтобы человек мог легко проверить.
  • Тесты на ноду не проверяют пустоту детей.

Архитектура 4/5

• Лучше все размеры в unit64_t. 32-битные файлы — это всего 4 ГБ, прошлый век.
• Tree
  • Непонятный метод Tree::getValue(). Не надо вводить лишнее состояние.
  • Tree::curNode — это не поле класса, а параметр внутренних методов. Не надо вводить лишнее состояние. Это как писать dfs на глобальных переменных.
  • Заодно надо избавиться от методов goLeft/goRight/goUp (они заменятся на простой иф, станет сильно проще читать) и не надо хранить parent.
• Huffman::Tree::Node можно определить прямо в HuffmanTree.cpp..?
• Non-movable Writer/Reader — это очень странно.
• Конструктор Iterator лучше всё-таки сделать приватным.
• Для бора имена goLeft/goRight звучат не так понятно, как go(bool).
  • Ещё раз уж они всегда должны работать (судя по assert(false)) давайте перенесём этот assert внутрь методов.
• Непонятно, зачем CharReader/CharWriter — их методы подсчёта символов нигде не нужны. А в HuffmanArchiver.cpp:109 можно просто length поставить (см. замечание по стилю про это место)
  • Но если уж их и оставлять, то давайте BitReader/BitWriter будут через них работать, а не сами считать байты.

Стиль 6/8

• const --> constexpr
• Если вы пытаетесь делать Bits общим и не зависеть от CHAR_BITS (я рекомендую считать, что это всегда 8 и захардкодить), то тесты должны делать так же, а там есть число 255.
  • Но у вас ещё потенциально поедет конструкция 1u << CHAR_BITS... Наверное... В общем, выпилите CHAR_BITS и предполагайте, что всегда 8 бит в char, пожалуйста, и добавьте на это static_assert.
• output1/output2 — compressed/extracted или что-то такое.
• getRandomFibonacciString — сделайте reserve
• По названию readAndCount неясно, что происходит с предыдущими данными в таблице.
• iterator.getValue().value() — что-то странное. Не должно быть надо так писать. Как минимум первый getValue() должен называться по-другому. А, следовательно, и в самой вершине тоже.
• uint32_t в качестве счётчика цикла, причём по умолчанию — ну такое, int гораздо лучше. Если везде размер uint32_t (а теперь будет 64) — окей, цикл по "размеру" тоже окей, но в общем случае надо всё-таки int.
  • А где-то у вас вообще цикл size_t i = 0; i < uint32_t O_O
• В конструкторе CLI можно не std::string, а string_view. Аналогично в параметрах сеттеров. Владение нужно уже только в полях.
• У потоков ввода-вывода надо ещё и делать clear() после seekg, кажется?
• HuffmanArchiver
  • while с if (...) { break; } в конце можно заменить на просто while
• NodeHeap: почему multiset?
  • NodePointer лучше принимать по значению
• Пустая строчка перед private:, public:, пожалуйста
• Tree::Tree
  • не хватает пустых строк между блоками for/if
  • Строчка 47: явно хочу assert в ветке else
  • Там же можно просто конструктор вызвать
• Node::Node — используйте member initialization list.
• Конструкторы Node/Iterator — noexcept
• ~BinaryWriter — лучше поставть assert, что все биты записаны. Иначе молчаливо для пользователя в момент уничтожения что-то дописываем в файл, у него может выравнивание поехать.
• flush()/dump() — очень путаются названия. flush() окей, но, возможно, стоит назвать метод, добавляющий нули, как-то явнее?
  • У dump/flush очень жёсткий инвариант: битов не слишком много. Пусть проверяют. А ещё лучше — вызывать их на каждый чих, а хитрые while перенести внутрь их.

[Egor Suvorov]

P.S. Код непортируемый: нужен бинарный режим файлов. Корректность 8/9.

[Карнаухов Кирилл]

• Конструктор CLI принимает const char**, чтобы ему сразу можно было отдать аргументы main. Мне показалось странным сначала требовать сделать какие-то манипуляции, чтобы отдать аргументы, а уже потом отдавать.